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]

A signed graph Γ = (G , σ) is obtained from a simple graph G by assigning to each edge of G a sign + or −. Let A (Γ) denote the adjacency matrix of Γ and α (G) be the independence number of G. We study the rank of A (Γ) and the independence number α (G) . We show that r (Γ) + 2 α (G) ≥ 2 n - 2 d (G) , where n is the order of G and d(G) is the dimension of the cycle space of G. Moreover, we obtain sharp lower bounds for r (Γ) + α (G) , r (Γ) - α (G) , r (Γ) / α (G) and we characterize all corresponding extremal graphs. [ABSTRACT FROM AUTHOR]

In this paper, we study a dynamic coloring of the vertices of a graph G that starts with an initial subset S of colored vertices, with all remaining vertices being uncolored. At each discrete time interval, a colored vertex with exactly one uncolored neighbor forces this uncolored neighbor to be colored. The initial set S is a zero forcing set of G if, by iteratively applying the forcing process, every vertex in G becomes colored. The zero forcing number Z(G) of G is the minimum cardinality of a zero forcing set of G. In this paper, we prove that if G is a connected, cubic, claw-free graph of order n ≥ 6 , then Z (G) ≤ α (G) + 1 where α (G) denotes the independence number of G. Further we prove that if n ≥ 10 , then Z (G) ≤ 1 3 n + 1 . Both bounds are shown to be best possible. [ABSTRACT FROM AUTHOR]

A set S⊆V(G) is a k-distance independent set of a graph G if the distance between every two vertices of S is greater than k. The k-distance independence number αk(G) of G is the maximum cardinality over all k-distance independent sets in G. A k-distance coloring of G is a function f from V(G) onto a set of positive integers (colors) such that for any two distinct vertices u and v at distance less than or equal to k we have f(u)≠f(v). The k-distance chromatic number of a graph G is the smallest number of colors needed to have a k-distance coloring of G. The k-distance independence numbers and 2-distance chromatic numbers of Cartesian products of cycles are considered. A computer-aided method with the isomorphic rejection is used to determine the k-distance independence numbers of Cartesian products of cycles. By using these results, several lower and upper bounds on the maximal cardinality AqL(n,d) of a q-ary Lee code of length n with a minimum distance at least d are improved. It is also established that the 2-distance chromatic number of G equals |V(G)|α(G2) for G=Cm□Cn□Ck, whenever k≥3 and (m,n)∈{(3,3),(3,4),(3,5),(4,4)} or k, m and n are all multiples of seven. Moreover, it is shown that the 2-distance chromatic number of the three-dimensional square lattice is equal to seven. [ABSTRACT FROM AUTHOR]

Let $$G$$ be a simple graph with $$n$$ vertices and $$G^c$$ be its complement. The matrix $$Q(G) = D(G) + A(G)$$ is called the signless Laplacian of $$G$$ , where $$D(G) = {\text {diag}}(d(v_1), d(v_2),..., d(v_n))$$ and $$A(G)$$ denote the diagonal matrix of vertex degrees and the adjacency matrix of $$G$$ , respectively. Let $$q_1(G)$$ be the largest eigenvalue of $$Q(G)$$ . We first give some upper and lower bounds on $$q_1(G)+q_1(G^c)$$ for a graph $$G$$ . Finally, lower and upper bounds are obtained for the clique number $$\omega (G)$$ and the independence number $$\alpha (G)$$ , in terms of the eigenvalues of the signless Laplacian matrix of a graph $$G$$ . [ABSTRACT FROM AUTHOR]