Search

A graph G is α -excellent if every vertex of G is contained in some maximum independent set of G. In this paper, we characterize α -excellent bipartite graphs, α -excellent unicyclic graphs, α -excellent simplicial graphs, α -excellent chordal graphs, α -excellent block graphs, and we show that every generalized Petersen graph is α -excellent. [ABSTRACT FROM AUTHOR]

The forest number f(G) of a graph G is max { | S | : S ⊆ V (G) and G[S] contains no cycle } . In this paper, we investigate the forest number of several kinds of products of two graphs G and H, such as cartesian product G □ H , direct product G × H and lexicographic product G[H]. The sharp bounds are given for Cartesian product and direct product of two graphs. However, characterizing all graphs attaining these bounds is difficult. Among other things, it is shown that (1) for any connected nontrivial graph G of order n with α (G) = 2 , and any nontrivial forest H, f (G □ H) = α (G) f (H) + 1 if and only if G ≅ K n - e and H ∈ { P 3 , P 4 } , or δ (G) = n - 2 and H ≅ K 2 . (2) f (G × K 2) = m + 1 for any graph G of order m with δ (G) ≥ m 2 + 1 . (3) For two nonempty graphs G and H, f (G [ H ]) = α (G) f (H) . In addition, a number of related conjectures are proposed. [ABSTRACT FROM AUTHOR]

For a positive integer k, a graph G is said to have the property I k if each component of G has independence number at most k. The I 1 -admission number of a graph G, denoted by η (G , I 1) , is the cardinality of a smallest vertex subset D such that V (G) = N G [ D ] or each component of G - N G [ D ] is a clique. In this paper, we show that for a connected graph G of order n, if G ∉ { P 3 , C 6 } , then η (G , I 1) ≤ 2 n 7 , and the bound is sharp. [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V and let b > a be two positive integers. We say that G has all [a, b]-factors if G has an h-factor for every h : V → N such that a ≤ h (v) ≤ b for every v ∈ V and ∑ v ∈ V h (v) ≡ 0 (mod 2) . A spanning subgraph F of G is called an (a, b)-parity factor, if d F (v) ≡ a ≡ b (mod 2) and a ≤ d F (v) ≤ b for all v ∈ V . In this paper, we have developed sufficient conditions for the existence of all [a, b]-factors and (a, b)-parity factors of G in terms of the independence number and connectivity of G. This work extended an earlier result of Nishimura (J Graph Theory 13: 63–69, 1989). Furthermore, we show that these results are best possible in some cases. [ABSTRACT FROM AUTHOR]

Let G be a graph of minimum degree at least two. A set D ⊆ V (G) is said to be a double total dominating set of G if | N (v) ∩ D | ≥ 2 for every vertex v ∈ V (G) . The minimum cardinality among all double total dominating sets of G is the double total domination number of G. In this article, we continue with the study of this parameter. In particular, we provide new bounds on the double total domination number in terms of other domination parameters. Some of our results are tight bounds that improve some well-known results. [ABSTRACT FROM AUTHOR]

For a connected graph G and a , b ∈ R , the general degree-eccentricity index is defined as DEI a , b (G) = ∑ v ∈ V (G) d G a (v) ecc G b (v) , where V(G) is the vertex set of G, d G (v) is the degree of a vertex v and ecc G (v) is the eccentricity of v in G. We obtain sharp upper and lower bounds on the general degree-eccentricity index for trees of given order in combination with given matching number, independence number, domination number or bipartition. The bounds hold for 0 < a < 1 and b > 0 , or for a > 1 and b < 0 . Many bounds hold also for a = 1 . All the extremal graphs are presented. [ABSTRACT FROM AUTHOR]