Search

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]

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]

We continue the study of (tw , ω) -bounded graph classes, that is, hereditary graph classes in which the treewidth can only be large due to the presence of a large clique, with the goal of understanding the extent to which this property has useful algorithmic implications for the Maximum Independent Set and related problems. In the previous paper of the series [Dallard, Milanič, and Štorgel, Treewidth versus clique number. II. Tree-independence number, J. Comb. Theory, Ser. B, 164 (2024) 404–442], we introduced the tree-independence number , a min-max graph invariant related to tree decompositions. Bounded tree-independence number implies both (tw , ω) -boundedness and the existence of a polynomial-time algorithm for the Maximum Weight Independent Packing problem, provided that the input graph is given together with a tree decomposition with bounded independence number. In particular, this implies polynomial-time solvability of the Maximum Weight Independent Set problem. In this paper, we consider six graph containment relations—the subgraph, topological minor, and minor relations, as well as their induced variants—and for each of them characterize the graphs H for which any graph excluding H with respect to the relation admits a tree decomposition with bounded independence number. The induced minor relation is of particular interest: we show that excluding either a K 5 minus an edge or the 4-wheel implies the existence of a tree decomposition in which every bag is a clique plus at most 3 vertices, while excluding a complete bipartite graph K 2 , q implies the existence of a tree decomposition with independence number at most 2 (q − 1). These results are obtained using a variety of tools, including ℓ -refined tree decompositions, SPQR trees, and potential maximal cliques, and actually show that in the bounded cases identified in this work, one can also compute tree decompositions with bounded independence number efficiently. Applying the algorithmic framework provided by the previous paper in the series leads to polynomial-time algorithms for the Maximum Weight Independent Set problem in an infinite family of graph classes, each of which properly contains the class of chordal graphs. In particular, these results apply to the class of 1-perfectly orientable graphs, answering a question of Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius from 2019. [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 G n , α be the set of all connected graphs of order n with independence number α. A graph is called the Q -minimizer graph (A -minimizer graph) if it attains the minimum signless Laplacian spectral radius (adjacency spectral radius) over all graphs in G n , α. In this paper, we first show that the Q -minimizer graph must be a tree for α ≥ ⌈ n 2 ⌉ , and then we derive seven propositions about the Q -minimizer graph. Moreover, when n − α is a constant, the structure of the Q -minimizer graph is characterized. The method of getting Q -minimizer graph in this paper is different from that of getting A -minimizer graph. As applications, we determine the Q -minimizer graphs for α = n − 1 , n − 2 , n − 3 and n − 4 , respectively. The results of α = n − 1 , n − 2 , n − 3 are consistent with that in Li and Shu (2010) [15] and the result of α = n − 4 is new. Interestingly, the Q -minimizer graph in G n , n − 4 is unique, which is exactly one of the A -minimizer graphs in G n , n − 4. [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]

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]

A twirling channel is a quantum channel induced by a continuous unitary representation π = ∑ i ⊕ m i π i on a compact group G , where π i are inequivalent irreducible representations. Motivated by a recent work [ 8 ] on minimal mixed unitary rank of Φ π , we explore the connections of the independence number, zero-error capacity, quantum codes, orthogonality index and phase retrievability of the quantum channel Φ π with the irreducible representation multiplicities m i and the irreducible representation dimensions dim H π i . In particular, we show that the independence number of Φ π is the sum of the multiplicities, the orthogonal index of Φ π is exactly the sum of those representation dimensions, and the zero-error capacity is equal to log (∑ i = 1 d m i ). We also present a lower bound for the phase retrievability in terms of the minimal length of phase retrievable frames for ℂ n [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]

Consider a graph on the non-singular matrices over a finite field, in which two distinct non-singular matrices are joined by an edge whenever their sum is singular. We prove an upper bound for the independence number of this graph. As a consequence, we obtain a lower bound for its chromatic number that significantly improves a previous result of Tomon. [ABSTRACT FROM AUTHOR]

In 2020, we initiated a systematic study of graph classes in which the treewidth can only be large due to the presence of a large clique, which we call (tw , ω) -bounded. The family of (tw , ω) -bounded graph classes provides a unifying framework for a variety of very different families of graph classes, including graph classes of bounded treewidth, graph classes of bounded independence number, intersection graphs of connected subgraphs of graphs with bounded treewidth, and graphs in which all minimal separators are of bounded size. While Chaplick and Zeman showed in 2017 that (tw , ω) -bounded graph classes enjoy some good algorithmic properties related to clique and coloring problems, it is an interesting open problem to which extent (tw , ω) -boundedness has useful algorithmic implications for problems related to independent sets. We provide a partial answer to this question by identifying a sufficient condition for (tw , ω) -bounded graph classes to admit a polynomial-time algorithm for the Maximum Weight Independent Packing problem and, as a consequence, for the weighted variants of the Independent Set and Induced Matching problems. Our approach is based on a new min-max graph parameter related to tree decompositions. We define the independence number of a tree decomposition T of a graph as the maximum independence number over all subgraphs of G induced by some bag of T. The tree-independence number of a graph G is then defined as the minimum independence number over all tree decompositions of G. Boundedness of the tree-independence number is a refinement of (tw , ω) -boundedness that is still general enough to hold for all the aforementioned families of graph classes. Generalizing a result on chordal graphs due to Cameron and Hell from 2006, we show that if a graph is given together with a tree decomposition with bounded independence number, then the Maximum Weight Independent Packing problem can be solved in polynomial time. Applications of our general algorithmic result to specific graph classes are given in the third paper of the series [Dallard, Milanič, and Štorgel, Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure]. [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 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]

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]

The pairwise balanced designs (PBD's) is a pair (P;B), where P is a finite set of v points and B is a family of subsets of P, called blocks such that every two distinct points in P appear in exactly one block. Let α(G) = α and β(G) = β be the vertex covering and independence number of a graph G = (V;E) with the minimum and maximum cardinality of such sets are denoted by α-sets and β-sets of G, respectively (or, simply (α; β)-sets). In this paper, we obtain the total number of (α; β)-sets in different jump sizes of some circulant graphs apart from strongly regular graphs which are the blocks of PBD. [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]

The independence number of a square matrix A , denoted by α (A) , is the maximum order of its principal zero submatrices. Given any integer n , let S n + be the set of n × n nonnegative symmetric matrices with zero diagonal. We characterize the linear maps on S n + preserving the independence number of all matrices in S n +. [ABSTRACT FROM AUTHOR]

For k ≥ 1 , the k -independence number α k of a graph is the maximum number of vertices that are mutually at distance greater than k. The well-known inertia and ratio bounds for the (1-)independence number α (= α 1) of a graph, due to Cvetković and Hoffman, respectively, were generalized recently for every value of k. We show that, for graphs with enough regularity, the polynomials involved in such generalizations are closely related and give exact values for α k , showing a new relationship between the inertia and ratio type bounds. Additionally, we investigate the existence and properties of the extremal case of sets of vertices that are mutually at maximum distance for walk-regular graphs. Finally, we obtain new sharp inertia and ratio type bounds for partially walk-regular graphs by using the predistance polynomials. [ABSTRACT FROM AUTHOR]

Let D(G) and A(G), respectively, be the diagonal matrix of vertex de- grees and the adjacency matrix of a connected graph G. The generalized adjacency matrix of G is defined as Aα(G) = αD(G) + (1 − α)A(G), α ∈ [0, 1]. The spread of the generalized adjacency matrix, denoted by S(Aα(G)), is defined as the difference of the largest and smallest eigenvalues of Aα(G). The spread S(Q(G)) of Q(G), the signless Laplacian matrix of G and S(A(G)) of A(G) are similarly defined. In this paper, we establish the relationships between S(Aα(G)), S(Q(G)) and S(A(G)). Further, we find bounds for S(Aα(G)) involving different parameters of G. Also, we obtain lower bounds for S(Aα(G)) in terms of the clique number and independence number of G, and we characterize the extremal graphs in some cases. [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]

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]

We propose new bounds on the domination number and on the independence number of a graph and show that our bounds compare favorably to recent ones. Our bounds are obtained by using the Bhatia-Davis inequality linking the variance, the expected value, the minimum, and the maximum of a random variable with bounded distribution. [ABSTRACT FROM AUTHOR]

The k-token graph Tk(G) is the graph whose vertices are the k-subsets of vertices of a graph G, with two vertices of Tk(G) adjacent if their symmetric difference is an edge of G. We explore when Tk(G) is a well-covered graph, that is, when all of its maximal independent sets have the same cardinality. For bipartite graphs G, we classify when Tk(G) is well-covered. For an arbitrary graph G, we show that if T2(G) is well-covered, then the girth of G is at most four. We include upper and lower bounds on the independence number of Tk(G), and provide some families of well-covered token graphs. [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]

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]

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]

In this paper, we consider the relations between three degree-based graph invariants, namely, the second Zagreb index M 2 (G) , forgotten index F (G) and Lanzhou index L z (G) for a general graph G and a tree T. We prove that for a graph G with independence number α (G) , there exists F (G) − L z (G) 2 α (G) ≤ M 2 (G) ≤ F (G) + L z (G) 2 with both equalities holding if and only if G is the complete graph or empty graph. Moreover, we prove that for a tree T , there exists M 2 (T) ≤ F (T) + L z (T) 3 with equality if and only if T is the path of order 3. [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]

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]

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]

The graphs with diameter equal to n − c , for 1 ⩽ c ⩽ 4 , which attain the minimum value with respect to the Harary index are being considered. Additionally, the sharp lower bound on Harary index of connected graphs with independence number equal to n − c , for 1 ⩽ c ⩽ 4 is derived. The extremal graphs are also characterized. [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]

A set S of vertices in a graph G is a paired dominating set if every vertex of G is adjacent to a vertex in S and the subgraph induced by S contains a perfect matching (not necessarily as an induced subgraph). The paired domination number, γ pr (G) , of G is the minimum cardinality of a paired dominating set of G. In this paper, we show that if T is a tree of order at least 2, then γ pr (T) ≤ 2 α (T) - φ (T) where α (T) is the independence number and φ (T) is the P 3 -packing number. We present a tight upper bound on the paired domination number of a tree T in terms of its maximum degree Δ . For Δ ≥ 1 , we show that if T is a tree of order n with maximum degree Δ , then γ pr (T) ≤ 5 Δ - 4 8 Δ - 4 n + 1 2 n 1 (T) + 1 4 n 2 (T) - Δ - 2 4 Δ - 2 , where n 1 (T) and n 2 (T) denote the number of vertices of degree 1 and 2, respectively, in T. Further, we show that this bound is tight for all Δ ≥ 3 . As a consequence of this result, if T is a tree of order n ≥ 2 , then γ pr (T) ≤ 5 8 n + 1 2 n 1 (T) + 1 4 n 2 (T) , and this bound is asymptotically best possible. [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]

In this paper we study relationships between the matching number, written μ(G), and the independence number, written α(G). Our first main result is to show α(G) ≤ μ(G) + |X| - μ(G[NG[X]]), where X is any intersection of maximum independent sets in G. Our second main result is to show δ(G)α(G) ≤ Δ(G)μ(G), where δ(G) and Δ(G) denote the minimum and maximum vertex degrees of G, respectively. These results improve on and generalize known relations between μ(G) and α(G). Further, we also give examples showing these improvements. [ABSTRACT FROM AUTHOR]

In this paper, we establish sharp upper and lower bounds for the size of connected graphs with fixed order and feedback number. Corresponding extremal graphs are also characterized. As a corollary, we give a sharp lower bound for the forest number of a graph in terms of its order and size, which extends a result of Shi and Xu (2017). [ABSTRACT FROM AUTHOR]

The simplicial rook graph SR (m , n) is the graph whose vertices are vectors in N m such that for each vector the summation of its coordinates is n and two vertices are adjacent if their corresponding vectors differ in exactly two coordinates. Martin and Wagner (Graphs Combin 31:1589–1611, 2015) asked about the independence number of SR (m , n) that is the maximum number of non-attacking rooks which can be placed on a (m - 1) -dimensional simplicial chessboard of side length n + 1 . In this work, we solve this problem and show that α (SR (m , n)) = (1 - o (1)) n + m - 1 n m . We also prove that for the domination number of rook graphs we have γ (SR (m , n)) = Θ (n m - 2) . Moreover we show that these graphs are Hamiltonian. The cyclic simplicial rook graph CSR (m , n) is the graph whose vertices are vectors in Z n m such that for each vector the summation of its coordinates modulo n is 0 and two vertices are adjacent if their corresponding vectors differ in exactly two coordinates. In this work we determine several properties of these graphs such as independence number, chromatic number and automorphism group. Among other results, we also prove that computing the distance between two vertices of a given CSR (m , n) is NP -hard in terms of n and m. [ABSTRACT FROM AUTHOR]

The open neighbourhood N(v) of a vertex v ∈ V; is the set of all vertices adjacent to v. Then N[v] = N(v)[fvg is called the enclave of v. We say that a vertex v ∈ V, n-covers an edge x ∈ X if x ∈ hN[v]i, the subgraph induced by the set N[v]. The n-covering number n(G) introduced by Sampathkumar and Neeralagi [18] is the minimum number of vertices needed to n-cover all the edges of G. In this paper one of the results proved in [18] is disproved by exhibiting an infinite class of graphs as counter example. Further, an expression for number of triangles in any graph is established. In addition, the properties of clique regular graphs has been studied. [ABSTRACT FROM AUTHOR]

A complex unit gain graph (or T -gain graph) is a triple Φ = (G , T , ϕ) (or (G , ϕ) for short) consisting of a simple graph G with | V (G) | = n , as the underlying graph of (G , ϕ) , the set of unit complex numbers T = { z ∈ C : | z | = 1 } and a gain function ϕ : E → → T with the property that ϕ (e i j) = ϕ (e j i ) − 1 = ϕ (e j i) ¯ . The adjacency matrix of (G , ϕ) is A (G , ϕ) = (a i j ) n × n , where a i j = ϕ (e i j) if v i is adjacent to v j and a i j = 0 otherwise. The rank of (G , ϕ) , denoted by r (G , ϕ) , is the rank of A (G , ϕ). Let α (G) and c (G) be the independence number and the cyclomatic number of G, respectively. In this paper, we prove that 2 n − 2 c (G) ≤ r (G , ϕ) + 2 α (G) ≤ 2 n. And the properties of the complex unit gain graphs that attain the lower bound are characterized. Furthermore, the lower and upper bounds on r (G , ϕ) + α (G) , r (G , ϕ) − α (G) and r (G , ϕ) α (G) are identified. These results generalize the corresponding known results about undirected graphs, mixed graphs, oriented graphs and signed graphs. [ABSTRACT FROM AUTHOR]

Given a graph G = (V;E), a set B = V (G) is a packing in G if the closed neighborhoods of every pair of distinct vertices in B are pairwise disjoint. The packing number (G) of G is the maximum cardinality of a packing in G. Similarly, open packing sets and open packing number are defined for a graph G by using open neighborhoods instead of closed ones. We give several results concerning the (open) packing number of graphs in this paper. For instance, several bounds on these packing parameters along with some Nordhaus-Gaddum inequalities are given. We characterize all graphs with equal packing and independence numbers and give the characterization of all graphs for which the packing number is equal to the independence number minus one. In addition, due to the close connection between the open packing and total domination numbers, we prove a new upper bound on the total domination number t(T) for a tree T of order n = 2 improving the upper bound t(T) = (n + s)=2 given by Chellali and Haynes in 2004, in which s is the number of support vertices of T. [ABSTRACT FROM AUTHOR]

Let r ≥ 3 be an integer and G be a graph. Let δ (G) , Δ (G) , α (G) , and μ (G) denote the minimum degree, maximum degree, independence number, and matching number of G , respectively. Recently, Caro, Davila and Pepper proved δ (G) α (G) ≤ Δ (G) μ (G). Mohr and Rautenbach characterized the extremal graphs within the classes of all non-regular graphs and 3-regular graphs. In this note, we characterize the extremal graphs within the classes of all r -regular graphs in terms of the Gallai–Edmonds Structure Theorem, which extends Mohr and Rautenbach's result. [ABSTRACT FROM AUTHOR]