Search

Copyright of Journal of Xinjiang University (Natural Science Edition) is the property of Xinjiang University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Harary and Wiener indices are distance-based topological index. In this paper, we study the relations of graph energy e(G) and its Harary index H(G) and Wiener index W(G). Moreover, for a given graph G we study the lower bound of H(G) e(G) and W(G) e(G) in terms of the number of vertices of G. [ABSTRACT FROM AUTHOR]

Let G be a k -uniform hypergraph with vertex set V (G) and edge set E (G). A connected and acyclic hypergraph is called a supertree. For 0 ≤ α < 1 , the α -spectral radius of G is the largest H -eigenvalue of α D (G) + (1 − α) A (G) , where D (G) and A (G) are the diagonal tensor of the degrees and the adjacency tensor of G , respectively. In this paper, we determine the unique supertrees with maximum α -spectral radius among all k -uniform supertrees with m edges and independence number β for ⌈ m (k − 1) + 1 k ⌉ ≤ β ≤ m , among all k -uniform supertrees with given degree sequences, and among all k -uniform supertrees with m edges and matching number μ for 1 ≤ μ ≤ ⌊ m (k − 1) + 1 k ⌋ , respectively. [ABSTRACT FROM AUTHOR]

The comaximal intersection graph CI(R) of ideals of a ring R is an undirected graph whose vertex set is the collection of all non-trivial (left) ideals of R and any two vertices I and J are adjacent if and only if I + J = R and I ∩ J 6= 0. We study the connectedness of CI(R). We also discuss independence number, clique number, domination number, chromatic number of CI(R). [ABSTRACT FROM AUTHOR]

Let G be a graph, and let λ (G) denote the smallest eigenvalue of G. First, we provide an upper bound for λ (G) based on induced bipartite subgraphs of G. Consequently, we extract two other upper bounds, one relying on the average degrees of induced bipartite subgraphs and a more explicit one in terms of the chromatic number and the independence number of G. In particular, motivated by our bounds, we introduce two graph invariants that are of interest on their own. Finally, special attention goes to the investigation of the sharpness of our bounds in various classes of graphs as well as the comparison with an existing well-known upper bound. [ABSTRACT FROM AUTHOR]

A k -CEC graph is a graph G which has connected domination number Yc(G) = k and Yc(G+uv) < k for every uv ∈ E(G). A k-CVC graph G is a 2-connected graph with γc(G) = k and γc(G - v) < k for any v ∈ V (G). A graph is said to be maximal k-CVC if it is both k-CEC and k-CVC. Let δ, κ, and α be the minimum degree, connectivity, and independence number of G, respectively. In this work, we prove that for a maximal 3-CVC graph, if α = κ, then κ = δ. We additionally consider the class of maximal 3-CVC graphs with α < κ and κ < δ, and prove that every 3-connected maximal 3-CVC graph when κ < δ is Hamiltonian connected. [ABSTRACT FROM AUTHOR]

Let C k (n) denote the family of all connected graphs of order n with chromatic number k. In this paper we show that the conjecture proposed by Tomescu which if x ≥ k ≥ 4 and G ∈ C k (n) , then P (G , x) ≤ (x) k (x - 1) n - k holds under the additional condition that G has an independent cut-set T of size at most 2 such that the number of components in G \ T is equal to the independence number of G. [ABSTRACT FROM AUTHOR]

Let G be a simple undirected connected graph, Tn,α be the set of trees with independence number α and order n. In this paper, we discuss the maximum reciprocal degree distance of trees in Tn,α and characterize the unique corresponding extremal graph. [ABSTRACT FROM AUTHOR]

For a positive integer k, a subset S of vertices of a graph G is k-independent if each vertex in S has at most k − 1 neighbors in S. We consider k-independent sets in two graph products: Cartesian and complementary prism. We show that the problem of determining k-independence remains NP-complete even for Cartesian products and complementary prisms. Furthermore, we present results on k-independence in the Cartesian product of two paths, known as grid graphs. [ABSTRACT FROM AUTHOR]

The cyclic graph Γ (S) of a semigroup S is the simple undirected graph whose vertex set is S and two vertices x , y are adjacent if the subsemigroup generated by x and y is monogenic. In this paper, we determine the clique number of Γ (S) for an arbitrary semigroup S. Further, we obtain the independence number of Γ (S) if S is a finite monogenic semigroup. At the final part of this paper, we give bounds for independence number of Γ (S) if S is a semigroup of bounded exponent and we also characterize the semigroups attaining the bounds. [ABSTRACT FROM AUTHOR]

We estimate the likely values of the chromatic and independence numbers of the random r-uniform d-regular hypergraph on n vertices for fixed r, large fixed d, and n → ∞. [ABSTRACT FROM AUTHOR]

We consider the following problem: for a given graph G and two integers k and d, can we apply a fixed graph operation at most k times in order to reduce a given graph parameter π by at least d? We show that this problem is NP-hard when the parameter is the independence number and the graph operation is vertex deletion or edge contraction, even for fixed d = 1 and when restricted to chordal graphs. We give a polynomial time algorithm for bipartite graphs when the operation is edge contraction, the parameter is the independence number and d is fixed. Further, we complete the complexity dichotomy for H-free graphs when the parameter is the clique number and the operation is edge contraction by showing that this problem is NP-hard in (C 3 + P 1) -free graphs even for fixed d = 1 . When the operation is edge deletion and the parameter is the chromatic number, we determine the computational complexity of the associated problem for cographs and complete multipartite graphs. Our results answer several open questions stated in Diner et al. (Theor Comput Sci 746:49–72, 2012, https://doi.org/10.1016/j.tcs.2018.06.023). [ABSTRACT FROM AUTHOR]

The concept of k -independent set, introduced by Fink and Jacobson in 1986, is a natural generalization of classical independence set. A k -independent set is a set of vertices whose induced subgraph has maximum degree at most k. The k -independence number of G , denoted by α k (G) , is defined as the maximum cardinality of a k -independent set of G. As a natural counterpart of the k -independence number, we introduced the concept of k -edge-independence number. An edge set M in E (G) is called k -edge-independent if the maximum degree of the subgraph induced by the edges in M is less or equal to k. The k -edge-independence number, denoted β k (G) , is defined as the maximum cardinality of a k -edge-independent set. In this paper, we study the Nordhaus–Gaddum-type results for the parameter α k (G) and β k (G). We obtain sharp upper and lower bounds of α k (G) + α r (G ¯) , α k (G) ⋅ α r (G ¯) , β k (G) + β r (G ¯) and β k (G) ⋅ β r (G ¯) for a graph G of order n. Some graph classes attaining these bounds are also given. [ABSTRACT FROM AUTHOR]

In this paper, we determine the graphs which have the minimal spectral radius among all the connected graphs of order n and the independence number ⌈ n 2 ⌉ - 1. [ABSTRACT FROM AUTHOR]

In this paper, we study the class of graphs G m , n that have the same degree sequence as two disjoint cliques K m and K n , as well as the class G ¯ m , n of the complements of such graphs. The problems of finding a maximum clique and a maximum independent set are NP-hard on G m , n . Therefore, looking for upper and lower bounds for the clique and independence numbers of such graphs is a challenging task. In this article, we obtain such bounds, as well as other related results. In particular, we consider the class of regular graphs, which are degree-equivalent to arbitrarily many identical cliques, as well as such graphs of bounded degree. [ABSTRACT FROM AUTHOR]

The atom-bond sum-connectivity (ABS) index of a graph G with edges e 1 , ... , e m is the sum of the numbers 1 − 2 ( d e i + 2) − 1 over 1 ≤ i ≤ m , where d e i is the number of edges adjacent to e i . In this article, we study the maximum values of the ABS index over graphs with given parameters. More specifically, we determine the maximum ABS index of connected graphs of a given order with a fixed (i) minimum degree, (ii) maximum degree, (iii) chromatic number, (iv) independence number, or (v) number of pendent vertices. We also characterize the graphs attaining the maximum ABS values in all of these classes. [ABSTRACT FROM AUTHOR]

Let G$$ G $$ be an n$$ n $$‐vertex graph, where δ(G)≥δn$$ \delta (G)\ge \delta n $$ for some δ:=δ(n)$$ \delta := \delta (n) $$. A result of Bohman, Frieze and Martin from 2003 asserts that if α(G)=Oδ2n$$ \alpha (G)=O\left({\delta}^2n\right) $$, then perturbing G$$ G $$ via the addition of ωlog(1/δ)δ3$$ \omega \left(\frac{\log \left(1/\delta \right)}{\delta^3}\right) $$ random edges, a.a.s. yields a Hamiltonian graph. We prove several improvements and extensions of the aforementioned result. In particular, keeping the bound on α(G)$$ \alpha (G) $$ as above and allowing for δ=Ω(n−1/3)$$ \delta =\Omega \left({n}^{-1/3}\right) $$, we determine the correct order of magnitude of the number of random edges whose addition to G$$ G $$ a.a.s. yields a pancyclic graph. Moreover, we prove similar results for sparser graphs, and assuming the correctness of Chvátal's toughness conjecture, we handle graphs having larger independent sets. Finally, under milder conditions, we determine the correct order of magnitude of the number of random edges whose addition to G$$ G $$ a.a.s. yields a graph containing an almost spanning cycle. [ABSTRACT FROM AUTHOR]

Let $ m_GI $ m G I denote the number of Laplacian eigenvalues of a graph G in an interval I and let $ \alpha (G) $ α (G) denote the independence number of G. In this paper, we determine the classes of graphs that satisfy the condition $ m_G[0,n-\alpha (G)]=\alpha (G) $ m G [ 0 , n − α (G) ] = α (G) when $ \alpha (G)= 2 $ α (G) = 2 and $ \alpha (G)= n-2 $ α (G) = n − 2 , where n is the order of G. When $ \alpha (G)=2 $ α (G) = 2 , $ G \cong K_1 \nabla K_{n-m} \nabla K_{m-1} $ G ≅ K 1 ∇ K n − m ∇ K m − 1 for some $ m \geq 2 $ m ≥ 2. When $ \alpha (G)=n-2 $ α (G) = n − 2 , there are two types of graphs $ B(p,q,r) $ B (p , q , r) and $ B'(p,q,r) $ B ′ (p , q , r) of order n = p + q + r + 2, which we call the binary star graphs. Also, we show that the binary star graphs with p = r are determined by their Laplacian spectra. [ABSTRACT FROM AUTHOR]

Let (P , ≤) be an atomic poset with the least element 0. The complement of the intersection graph of ideals of P , denoted by Γ (P) , is defined to be a graph whose vertices are all non-trivial ideals of P and two distinct vertices I and J are adjacent if and only if I ∩ J = { 0 }. In this paper, we consider the complement of the intersection graph of ideals of a poset. We prove that Γ (P) is totally disconnected or diam (Γ (P) \) ∈ { 1 , 2 , 3 } , where is the set of all isolated vertices of Γ (P). We show that g r (Γ (P)) ∈ { 3 , 4 , ∞ }. Also, we characterize all posets whose complement of the intersection graph is forest, unicyclic or complete r -partite graph. Among other results, we prove that Γ (P) is weakly perfect; and it is perfect if and only if | Atom (P) | ≤ 4. Finally, we show that Γ (P) is class 1 , where P = Atom (P) ∪ { 0 }. [ABSTRACT FROM AUTHOR]

In this paper, we prove that every simple connected graph with α > n 2 has 1 as a normalized Laplacian eigenvalue with multiplicity at least 2 α − n , where n and α are the order and the independence number of the graph, respectively. Then we investigate graphs with α ≤ n 2 and having or not having 1 as a normalized Laplacian eigenvalue. [ABSTRACT FROM AUTHOR]

In this paper, we give a class of graphs that do not admit disjoint maximum and maximal independent (MMI) sets. The concept of inverse independence was introduced by Bhat and Bhat in [Inverse independence number of a graph, Int. J. Comput. Appl. 42(5) (2012) 9–13]. Let A be a α -set in G. An independent set D ⊂ V (G) − A is called an inverse independent set with respect to A. The inverse independence number α − 1 (G) is the size of the largest inverse independent set in G. Bhat and Bhat gave few bounds on the independence number of a graph, we continue the study by giving some new bounds and exact value for particular classes of graphs: spider tree, the rooted product and Cartesian product of two particular graphs. [ABSTRACT FROM AUTHOR]

Let G be a finite group and A G be the automorphism group of G (i.e. Aut (G)). We associated a bipartite graph, denoted by Γ G , to G and its automorphism group Aut (G) as follows: two parts of the vertex set are G \ L (G , Z (G)) and A G \ Aut c (G) , where L (G , Z (G)) is the set of elements g ∈ G such that g − 1 α (g) ∈ Z (G) for all α ∈ A G and Aut c (G) is the set of automorphisms β ∈ A G such that g − 1 β (g) ∈ Z (G) for all g ∈ G. Two vertices g ∈ G \ L (G , Z (G)) and α ∈ A G \ Aut c (G) are adjacent if and only if g − 1 α (g) ∉ Z (G). In this paper, we investigate some fundamental properties of Γ G such as connectivity, diameter, girth, Hamiltonian, independence and dominating numbers. Moreover, planarity and outer planarity of the graph are studied. [ABSTRACT FROM AUTHOR]

We consider a family of distance graphs in R n and find its independence numbers in some cases. Define the graph J ± (n , k , t) in the following way: the vertex set consists of all vectors from { - 1 , 0 , 1 } n with exactly k nonzero coordinates; edges connect the pairs of vertices with scalar product t. We find the independence number of J ± (n , k , t) for an odd negative t and n > n 0 (k , t) . [ABSTRACT FROM AUTHOR]

Let S be a Clifford semigroup and A a subset of S. We write C a y (S , A) for the Cayley digraph of a Clifford semigroup S relative to A. The (weak, path, weak path) independence number of a graph is the maximum cardinality of an (weakly, path, weakly path) independent set of vertices in the graph. In this paper, we characterize maximal connected subdigraphs of C a y (S , A) and apply these results to determine the (weak, path, weak path) independence number of C a y (S , A) . [ABSTRACT FROM AUTHOR]

In view of this paper, we have defined Rough Co-zero divisor graph G (Z ∗ (J)) of a rough semiring (T , Δ , ∇) for a given approximation space I = (U , R) where U is nonempty finite set of objects and R is an arbitrary equivalence relation on U. It is proved that the Rough Co-zero divisor graph and the subgraph of Rough Ideal-based rough edge Cayley graph G (T ∗ (J)) are complement to each other. Also the Clique number and Independence number of G (T ∗ (J)) and G (Z ∗ (J)) are obtained. The developed concepts are illustrated with suitable examples. A sentiment analysis is also made using G (T ∗ (J)) for a Twitter data. [ABSTRACT FROM AUTHOR]

Given a graph G, the adjacency matrix and degree diagonal matrix of G are denoted by A(G) and D(G), respectively. In 2017, Nikiforov[24] proposed the Aα-matrix: Aα(G) = αD(G) + (1 − α)A(G), where α ∈ [0, 1]. The largest eigenvalue of this novel matrix is called the Aα-index of G. In this paper, we characterize the graphs with minimum Aα-index among n-vertex graphs with independence number i for α ∈ [0, 1), where i = 1 , ⌊ n 2 ⌋ , ⌈ n 2 ⌉ , ⌊ n 2 ⌋ + 1 , n − 3 , n − 2 , n − 1 , whereas for i = 2 we consider the same problem for α ∈ [ 0 , 3 4 ] . Furthermore, we determine the unique graph (resp. tree) on n vertices with given independence number having the maximum Aα-index with α ∈ [0, 1), whereas for the n-vertex bipartite graphs with given independence number, we characterize the unique graph having the maximum Aα-index with α ∈ [ 1 2 , 1) . [ABSTRACT FROM AUTHOR]

A subgraph of a graph G is spanning if the subgraph covers all vertices of G. A path- factor of a graph G is a spanning subgraph H of G such that every component of H is a path. In this article, we prove that (i) a connected graph G with δ(G) ≥ 5 admits a {P2, P5}-factor if G satisfies δ(G) > 3α(G)-1/4 δ G > 3 α G - 1 4 $ \delta (G)>\frac{3\alpha (G)-1}{4}$ ; (ii) a connected graph G of order n with n ≥ 7 has a {P2, P5}-factor if G satisfies max{dG(x), dG(y)} ≥ 3n/7 ≥ 3 n 7 $ \ge \frac{3n}{7}$ for any two nonadjacent vertices x and y of G. [ABSTRACT FROM AUTHOR]

For a given graph H , the independence number α (H) of H is the size of the maximum independent set of V (H). Finding the maximum independent set in a graph is NP-hard. Another version of the independence number is defined as the size of the maximum-induced forest of H , and called the forest number of H , and denoted by f (H). Finding f (H) is also an NP-hard problem. Suppose that H = (V (H) , E (H)) is a graph, and is a family of graphs, a graph H has a -free k -coloring if there exists a decomposition of V (H) into sets V i , i = 1 , 2 , ... , k , so that G ⊈ H [ V i ] for each i , and each G ∈ . S ⊆ V (H) is G -free, if the subgraph of H induced by S is G -free, i.e., it contains no copy of G. Finding a maximum subset S of H , such that H [ S ] is a G -free graph is a very hard problem as well. In this paper, we study the generalized version of the independence number of a graph. Also, we give some bounds about the size of the maximum G -free subset of graphs as another purpose of this paper. [ABSTRACT FROM AUTHOR]

For a set H of connected graphs, a spanning subgraph H of G is called an H -factor of G if each component of H is isomorphic to an element of H . A graph G is called an H -factor uniform graph if for any two edges e 1 and e 2 of G, G has an H -factor covering e 1 and excluding e 2 . Let each component in H be a path with at least d vertices, where d ≥ 2 is an integer. Then an H -factor and an H -factor uniform graph are called a P ≥ d -factor and a P ≥ d -factor uniform graph, respectively. In this article, we verify that (i) a 2-edge-connected graph G is a P ≥ 3 -factor uniform graph if δ (G) > α (G) + 4 2 ; (ii) a (k + 2) -connected graph G of order n with n ≥ 5 k + 3 - 3 5 γ - 1 is a P ≥ 3 -factor uniform graph if | N G (A) | > γ (n - 3 k - 2) + k + 2 for any independent set A of G with | A | = ⌊ γ (2 k + 1) ⌋ , where k is a positive integer and γ is a real number with 1 3 ≤ γ ≤ 1 . [ABSTRACT FROM AUTHOR]

A graph G is called semi square stable if α(G²) = i(G) where α(G²) is the independence number of G² and i(G) is the independent dominating number of G. A subset S of the vertex set of a graph G is an efficient dominating set if S is an independent set and every vertex of G is either in S or adjacent to exactly one vertex of S: In this paper, we show that every square stable graph has an efficient dominating set and if a graph has an efficient dominating set, then it is semi square stable. We characterize when the join and the corona product of two disjoint graphs are semi square sable graphs and when they have efficient dominating sets. [ABSTRACT FROM AUTHOR]

Let T be a tree. The sets of leaves and branch vertices of T are denoted by L(T) and B(T), respectively. For two distinct vertices u, v of T, let P T [ u , v ] denote the unique path in T connecting u and v. When B (T) ≠ ∅ , we call the graph S T = ⋃ u , v ∈ B (T) P T [ u , v ] the internal subtree of T. In this paper, we give two conditions for a connected graph to have a spanning tree whose internal subtree has few branch vertices and leaves. Moreover, the sharpness of our result is also shown. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with non-zero identity. Khojasteh and Nikmehr (Can. Math. 60(2), 319–328, 2017) introduced the weakly nilpotent graph Γ w (R) of a commutative ring R, whose vertices are R ∗ = R \ { 0 } and two distinct vertices x and y are adjacent if and only if x y ∈ N (R) ∗ , where N (R) ∗ is the set of all non-zero nilpotent elements of R. In this paper, we extend some more results such as the connectedness, the completeness, the bipartiteness and the domination number of Γ w (R) . We also study some properties on the complement of the weakly nilpotent graph Γ w (R) ¯ of a commutative ring. [ABSTRACT FROM AUTHOR]

Win proved a very famous conclusion that states the graph G with connectivity κ (G) , independence number α (G) and α (G) ≤ κ (G) + k − 1 (k ≥ 2) contains a spanning k-ended tree. This means that there exists a spanning tree with at most k leaves. In this paper, we strengthen the Win theorem to the following: Let G be a simple 2-connected graph such that | V (G) | ≥ 2 κ (G) + k , α (G) ≤ κ (G) + k (k ≥ 2) and the number of maximum independent sets of cardinality κ + k is at most n − 2 κ − k + 1 . Then, either G contains a spanning k-ended tree or a subgraph of K κ ∨ ((k + κ − 1) K 1 ∪ K n − 2 κ − k + 1) . [ABSTRACT FROM AUTHOR]

Simplicial complexes are a popular tool used to model higher-order interactions between elements of complex social and biological systems. In this paper, we study some combinatorial aspects of a class of simplicial complexes created by a graph product, which is an extension of the pseudo-fractal scale-free web. We determine explicitly the independence number, the domination number, and the chromatic number. Moreover, we derive closed-form expressions for the number of acyclic orientations, the number of root-connected acyclic orientations, the number of spanning trees, as well as the number of perfect matchings for some particular cases. [ABSTRACT FROM AUTHOR]

Let S be a connected graph with Steiner number S(S). A decomposition S = {S!, S", …, S#} is said to be a Steiner decomposition if S(G) = S(Gi) for all S (1 ≤ i ≤ n). The maximum cardinality obtained for the Steiner decomposition S of S is called the Steiner decomposition number of S and is denoted by S(G). In this paper we present a relation between Steiner decomposition number and independence number of S. Steiner decomposition number for some power of paths are discussed. It is also shown that given any pair S, S of positive integers with S ≥ 2 there exists a connected graph S such that G(S) = m and Sst (G) = n. [ABSTRACT FROM AUTHOR]

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]

Let f : V (G) → {0, 1, 2} be a function on a graph G with vertex set V (G). Let Vi = {v ∈ V (G) : f (v) = i} for every i ∈ {0, 1, 2}. The function f is said to be an independent Roman dominating function on G if V1 ∪ V2 is an independent set and for every υ 2 V0. The minimum weight among all independent Roman dominating functions f on G is the independent Roman domination number of G, and is denoted by iR(G). In this paper we continue with the study of this parameter. In particular, we provide new bounds on iR(G) in terms of other domination invariants. Some of our results are tight bounds that improve some well-known results. Finally, we compute the independent Roman domination number of some product graphs, and we provide an alternative proof to show that the problem of computing iR(G) is NP-hard. [ABSTRACT FROM AUTHOR]

It was conjectured by Jaeger et al. that all 5-edge-connected graphs are Z3-connected. In this paper, we confirm this conjecture for all 5-edge-connected graphs with independence number at most 3. [ABSTRACT FROM AUTHOR]

The asymptotic behavior of general independence numbers of random hypergraphs for the binomial model is studied. We prove that for some types of parameter variations the distribution of independence numbers is concentrated on two neighboring values. [ABSTRACT FROM AUTHOR]

In mathematical chemistry, molecular descriptors serve an important role, primarily in quantitative structure–property relationship (QSPR) and quantitative structure–activity relationship (QSAR) studies. A topological index of a molecular graph is a real number that is invariant under graph isomorphism conditions and provides information about its size, symmetry, degree of branching, and cyclicity. For any graph N, the first and second Gourava indices are defined as G O 1 (N) = ∑ u ′ v ′ ∈ E (N) (d (u ′) + d (v ′) + d (u ′) d (v ′) ) and G O 2 (N) = ∑ u ′ v ′ ∈ E (N) (d (u ′) + d (v ′)) d (u ′) d (v ′) , respectively.The independence number of a graph N, being the cardinality of its maximal independent set, plays a vital role in reading the energies of chemical trees. In this research paper, it is shown that among the family of trees of order δ and independence number ξ , the spur tree denoted as Υ δ , ξ maximizes both 1st and 2nd Gourava indices, and with these characterizations this graph is unique. [ABSTRACT FROM AUTHOR]

We study several parameters of a random Bienaymé–Galton–Watson tree $T_n$ of size $n$ defined in terms of an offspring distribution $\xi$ with mean $1$ and nonzero finite variance $\sigma ^2$. Let $f(s)=\mathbb{E}\{s^\xi \}$ be the generating function of the random variable $\xi$. We show that the independence number is in probability asymptotic to $qn$ , where $q$ is the unique solution to $q = f(1-q)$. One of the many algorithms for finding the largest independent set of nodes uses a notion of repeated peeling away of all leaves and their parents. The number of rounds of peeling is shown to be in probability asymptotic to $\log n/\log (1/f'(1-q))$. Finally, we study a related parameter which we call the leaf-height. Also sometimes called the protection number, this is the maximal shortest path length between any node and a leaf in its subtree. If $p_1 = \mathbb{P}\{\xi =1\}\gt 0$ , then we show that the maximum leaf-height over all nodes in $T_n$ is in probability asymptotic to $\log n/\log (1/p_1)$. If $p_1 = 0$ and $\kappa$ is the first integer $i\gt 1$ with $\mathbb{P}\{\xi =i\}\gt 0$ , then the leaf-height is in probability asymptotic to $\log _\kappa \log n$. [ABSTRACT FROM AUTHOR]

For graph G with vertex set V and u ∈ V , we write d u to be the degree of u. For ∅ ≠ S ⊆ V , the independence ratio of S is defined as ρ (S) = min { α (T) | T | : ∅ ≠ T ⊆ S } , where α (T) is the independence number of the graph induced by T in G. Let N i (u) = { w ∈ V : d i s t (u , w) = i } . We shall show that if ρ 0 > 0 and a graph G has ρ (N i (u)) ≥ ρ 0 for each u ∈ V and i ≤ k , then its independence number is at least a ∑ u d u 1 / (k - 1) (k - 1) / k , where a = a (k , ρ 0) > 0 is independent of G. This result generalizes some former results for graphs with forbidden odd cycles. [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]

The Merrifield-Simmons index σ is the total number of independent vertex sets (including the empty set) of the graph G. The Wiener index W is the sum of distances in all unordered pairs of vertices of G. We construct some new graphs satisfying σ > W and W > σ, respectively. In particular, infinite graphs satisfying W > σ are invented with graphs with diameter 2 and infinite ones satisfying σ > W are discovered with so-called universally diametrical graphs. [ABSTRACT FROM AUTHOR]

A path-factor in a graph G is a spanning subgraph F of G such that every component of F is a path. Let d and n be two nonnegative integers with d ≥ 2. A P≥d-factor of G is its spanning subgraph each of whose components is a path with at least d vertices. A graph G is called a P≥d-factor covered graph if for any e ∈ E(G), G admits a P≥d-factor containing e. A graph G is called a (P≥d, n)-factor critical covered graph if for any N ⊆ V(G) with |N| = n, the graph G − N is a P≥d-factor covered graph. A graph G is called a P≥d-factor uniform graph if for any e ∈ E(G), the graph G − e is a P≥d-factor covered graph. In this paper, we verify the following two results: (i) An (n + 1)-connected graph G of order at least n + 3 is a (P≥3, n)-factor critical covered graph if G satisfies δ(G) > (α(G)+2n+3)/2 δ (G) > α (G) + 2 n + 3 2 $ \delta (G)>\frac{\alpha (G)+2n+3}{2}$ ; (ii) Every regular graph G with degree r ≥ 2 is a P≥3-factor uniform graph. [ABSTRACT FROM AUTHOR]

We present two greedy algorithms that determine zero-error codes and lower bounds on the zero-error capacity. These algorithms have many advantages, e.g., they do not store a whole product graph in a computer memory and they use the so-called distributions in all dimensions to get better approximations of the zero-error capacity. We also show an additional application of our algorithms. [ABSTRACT FROM AUTHOR]

The power graph P G of a finite group G is the graph whose vertex set is G, two distinct vertices are adjacent if one is a power of the other. The order supergraph S G of P G is the graph with vertex set G, and two distinct vertices x, y are adjacent if o(x)|o(y) or o(y)|o(x). In this paper, we study the independence number of S G and answer a question was posed by Hamzeh and Ashrafi. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with identity and Nil(r) be the set of nilpotent elements of r. The nil-graph of ideals of r is defined as the graph AGN(R) whose vertex set is {I: (0) ≠ I ⊲ RR and there exists a non-trivial ideal J such that IJ ⊆ Nil(r)} and two distinct vertices I and J are adjacent if and only if IJ ⊆ Nil(R). Here, we study conditions under which AGN(R) is complete or bipartite. Also, the independence number of AGN(R) is determined, where R is a reduced ring. Finally, we classify Artinian rings whose nil-graphs of ideals have genus at most one. [ABSTRACT FROM AUTHOR]

Combining the concept of a fractional (g, f)-covered graph with that of a fractional ID-(g, f)-factor-critical graph, we define the concept of a fractional ID-(g, f)-factor-critical covered graph. This paper reveals the relationship between some graph parameters and the existence of fractional ID-(g, f)-factor-critical covered graphs. A sufficient condition for a graph being a fractional ID-(g, f)-factor-critical covered graph is presented. In addition, we demonstrate the sharpness of the main result in this paper by constructing a special graph class. Furthermore, the relationship between other graph parameters(such as binding number, toughness, sun toughness and neighborhood union) and fractional ID-(g, f)-factor-critical covered graphs can be studied further. [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]