Search

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]

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]

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]

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]

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]

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]

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]

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]

In this paper the problem of maximizing vertex-degree function index H f (G) for trees and unicyclic graphs G of order n and independence number s is solved for strictly convex functions f (x). In the case of unicyclic graphs f (x) must also satisfy strict inequality f (4) + 3 f (2) > 3 f (3) + f (1). These conditions are fulfilled by general first Zagreb index 0 R α (G) for α > 2 , second multiplicative Zagreb index ∏ 2 (G) and sum lordeg index S L (G). The extremal graphs are unique and they are stars or have diameter equal to three or to four. The same results are valid for the corresponding minimization problem when f (x) is strictly concave and the inequality is reversed. [ABSTRACT FROM AUTHOR]

Jianguo Qian, Konrad Engel and Wei Xu (Dass et al., 2015) gave a generalization of Sperner's theorem (Sperner, 1928): n and m are given integers, they found the minimum number of pairs Y i ⊆ Y j (i ≠ j) in a multifamily { Y 1 , ... , Y m } of not necessarily different subsets of an n -element set. Here a far reaching generalization and easier proof is given. Let G be a graph and m an integer, choose m vertices with possible repetitions in such a way that the number of adjacent pairs (including the repeated vertices) is minimum. It is proved that the following choice gives the minimum: take the vertices of a largest independent set in G with nearly equal multiplicities. [ABSTRACT FROM AUTHOR]

The independence number, coloring number and related parameters are investigated in the setting of oriented hypergraphs using the spectrum of the normalized Laplace operator. For the independence number, both an inertia–like bound and a ratio–like bound are shown. A Sandwich Theorem involving the clique number, the vector chromatic number and the coloring number is proved, as well as a lower bound for the vector chromatic number in terms of the smallest and the largest eigenvalue of the normalized Laplacian. In addition, spectral partition numbers are studied in relation to the coloring number. [ABSTRACT FROM AUTHOR]

A dominating set X in a graph G is secure if for each u ∈ V (G) − X , there exists a neighbor x of u in X such that (X − { x }) ∪ { u } is a dominating set. The secure domination number of G is the order of a smallest secure dominating set and denoted by γ s (G). Let β (G) be the independence number of G. In this note, we remark that every C 5 -free G satisfies γ s (G) ≤ β (G). This inequality unifies and extends several known results. [ABSTRACT FROM AUTHOR]

Hoffman's ratio bound is an upper bound for the independence number of a regular graph in terms of the eigenvalues of the adjacency matrix. The bound has proved to be very useful and has been applied many times. Hoffman did not publish his result, and for a great number of users the emergence of Hoffman's bound is a black hole. With his note I hope to clarify the history of this bound and some of its generalizations. [ABSTRACT FROM AUTHOR]

Let G (n , α) be the class of block graphs on n vertices and prescribed independence number α. In this article we prove that the maximum spectral radius ρ (G) , among all graphs G ∈ G (n , α) , is reached at a unique graph. As a byproduct we obtain an upper for ρ (G) , when G ∈ G (n , α). [ABSTRACT FROM AUTHOR]

We identify the mean growth of the independence number of random binary search trees and random recursive trees and show normal fluctuations around their means. Similarly we also show normal limit laws for the domination number and variations of it for these two cases of random tree models. Our results are an application of a recent general theorem of Holmgren and Janson on fringe trees in these two random tree models. [ABSTRACT FROM AUTHOR]

The total number of independent subsets, including the empty set, of a graph, is also termed as the Merrifield–Simmons index (M S I) in mathematical chemistry. The eccentric complexity of a graph G is defined to be the number of different eccentricities of its vertices. Hua et al. (2020) mentioned two open problems and a conjecture on the Merrifield–Simmons index and eccentric complexity of graph. In this paper we solve both open problems and a conjecture. Moreover, we generalize some of the results. [ABSTRACT FROM AUTHOR]

Based on the well-known cardinal characteristics s , r and i , we introduce nine related cardinal characteristics by using the notion of asymptotic density to characterise different intersection properties of infinite sets. We prove several bounds and consistency results, e.g. the consistency of s < s 1 2 , as well as several results about possible values of i 1 2 . [ABSTRACT FROM AUTHOR]

We obtain new upper and lower bounds for the independence number and the chromatic number of generalized preferential attachment graphs. [ABSTRACT FROM AUTHOR]

A k -ended tree is a tree with at most k leaves. In this note, we give a simple proof for the following theorem. Let G be a connected graph and k be an integer (k ≥ 2). Let S be a vertex subset of G such that α G (S) ≤ k + κ G (S) − 1. Then, G has a k -ended tree which covers S. Moreover, the condition is sharp. [ABSTRACT FROM AUTHOR]

Combinatorial problems are a fundamental research subject of theoretical computer science, and for a general graph many combinatorial problems are NP-hard and even #P-complete. Thus, it is interesting to seek or design special graphs for which these difficult combinatorial problems can be exactly solved. In this paper, we study some combinatorial problems for the Farey graphs, which are translated from Farey sequences and have received considerable attention from the scientific community. We determine exactly the domination number, the independence number, and the matching number. Moreover, we derive exact or recursive solutions to the number of minimum dominating sets, the number of dominating sets, the number of maximum independent sets, the number of independent sets, the number of maximum matchings, as well as the number of matchings. Finally, we obtain explicit expressions for the number of acyclic orientations and the number of root-connected acyclic orientations. Since the considered combinatorial problems have found wide applications in diverse fields, such as network science and graph data miming, this work is helpful for deepening our understanding of the applications for these combinatorial problems. [ABSTRACT FROM AUTHOR]

Identifying graphs with extremal properties is an extensively studied topic in both topological graph theory and spectral graph theory. As observed in the literature, for many graph categories the extremal graphs with respect to some prescribed topological index or spectral invariant are the same. Therefore, it is an interesting problem to find a unified method to identify the extremal graphs for a set of topological or spectral invariants. Here we consider the majorization theorem to obtain extremal graphs in the class of trees, unicyclic graphs and bicyclic graphs with given order and fixed maximum degree, independence number, matching number, domination number, and/or number of pendant vertices, respectively. [ABSTRACT FROM AUTHOR]

A hole in a graph is an induced cycle of length at least 4. Let s ≥ 2 and t ≥ 2 be integers. A graph G is (s , t) - splittable if V (G) can be partitioned into two sets S and T such that χ (G [ S ]) ≥ s and χ (G [ T ]) ≥ t. The well-known Erdős–Lovász Tihany Conjecture from 1968 states that every graph G with ω (G) < χ (G) = s + t − 1 is (s , t) -splittable. This conjecture is hard, and few related results are known. However, it has been verified to be true for line graphs, quasi-line graphs, and graphs with independence number 2. In this paper, we establish more evidence for the Erdős–Lovász Tihany Conjecture by showing that every graph G with α (G) ≥ 3 , ω (G) < χ (G) = s + t − 1 , and no hole of length between 4 and 2 α (G) − 1 is (s , t) -splittable, where α (G) denotes the independence number of a graph G. [ABSTRACT FROM AUTHOR]

The size of a largest independent set of vertices in a given graph G is denoted by α (G) and is called its independence number (or stability number). Given a graph G and an integer K , it is NP-complete to decide whether α (G) ≥ K. An upper bound for the independence number α (G) of a given graph G with n vertices and m edges is given by α (G) ≤ p ≔ ⌊ 1 2 + 1 4 + n 2 − n − 2 m ⌋. In this paper we will consider maximum independent sets near this upper bound. Our main result is the following: There exists an algorithm with time complexity O (n 2) that, given as an input a graph G with n vertices, m edges, p ≔ ⌊ 1 2 + 1 4 + n 2 − n − 2 m ⌋ , and an integer k ≥ 0 with p ≥ 2 k + 1 , returns an induced subgraph G p , k of G with n 0 ≤ p + 2 k + 1 vertices such that α (G) ≤ p − k if and only if α (G p , k) ≤ p − k. Furthermore, we will show that we can decide in time O (1. 273 8 3 k + n 2) whether α (G p , k) ≤ p − k. [ABSTRACT FROM AUTHOR]

• For any connected graph G, α (G) ≤ m G [ 0 , n − α (G) ]. • We classify graph where the equality holds for α (G) = 3 or n − 3. • When α (G) = 3 , we used the result of Zhang and Luo. • When α (G) = n − 3 , we give a numerical criterion using the characteristic polynomial of graphs. For a graph G , let α (G) be the independence number of G , let L (G) be the Laplacian matrix of G , and let m G I be the number of eigenvalues of L (G) in the interval I. Ahanjideh, Akbari, Fakharan and Trevisan proved that α (G) ≤ m G [ 0 , n − α (G) ] if G is an n -vertex connected graph. Choi, Moon and Park characterized graphs with α (G) = m G [ 0 , n − α (G) ] for α (G) = 2 and α (G) = n − 2. In this paper, we give a characterization for α (G) = 3 and α (G) = n − 3. [ABSTRACT FROM AUTHOR]

Abstract Let G be a connected graph. The eccentricity e (v) of a vertex v is the distance from v to a vertex farthest from v. The average eccentricity avec (G) of G is defined as the average of the eccentricities of the vertices of G , i.e., as 1 | V | ∑ v ∈ V e (v) , where V is the vertex set of G. For k ∈ N , the k -packing number of G is the largest cardinality of a set of vertices of G whose pairwise distance is greater than k. A k -dominating set of G is a set S of vertices such that every vertex of G is within distance k from some vertex of S. The k -domination number (connected k -domination number) of G is the minimum cardinality of a k -dominating set (of a k -dominating set that induces a connected subgraph) of G. For k = 1 , the k -packing number, the k -domination number and the connected k -domination number are the independence number, the domination number and the connected domination number, respectively. In this paper we present upper bounds on the average eccentricity of graphs in terms of order and either k -packing number, k -domination number or connected k -domination number. [ABSTRACT FROM AUTHOR]

Abstract We study the independence number of a product of Kneser graph K (n , k) with itself, where we consider all four standard graph products. The cases of the direct, the lexicographic and the strong product of Kneser graphs are not difficult (the formula for α (K (n , k) ⊠ K (n , k)) is presented in this paper), while the case of the Cartesian product of Kneser graphs is much more involved. We establish a lower bound and an upper bound for the independence number of K (n , 2) □ K (n , 2) , which are asymptotically tending to n 3 ∕ 3 and 3 n 3 ∕ 8 , respectively. The former is obtained by a construction, which differs from the standard diagonalization procedure, while for the upper bound the ℓ -independence number of Kneser graphs can be applied. We also establish some constructions in odd graphs K (2 k + 1 , k) , which give a lower bound for the 2-independence number of these graphs, and prove that two such constructions give the same lower bound as a previously known one. Finally, we consider the s -stable Kneser graphs K (k s + 1 , k) s − stab , derive a formula for their ℓ -independence number, and give the exact value of the independence number of the Cartesian square of K (k s + 1 , k) s − stab. [ABSTRACT FROM AUTHOR]

Abstract Fricke, Hedetniemi, Hedetniemi, and Hutson asked whether every tree with domination number γ has at most 2 γ minimum dominating sets. Bień gave a counterexample, which allows us to construct forests with domination number γ and 2. 059 8 γ minimum dominating sets. We show that every forest with domination number γ has at most 2. 460 6 γ minimum dominating sets, and that every tree with independence number α has at most 2 α − 1 + 1 maximum independent sets. [ABSTRACT FROM AUTHOR]

Abstract Given a connected graph G = (V G , E G) , the eccentricity distance sum (EDS) of G is defined as ξ d (G) = ∑ { u , v } ⊆ V G (ε (u) + ε (v)) d G (u , v) and the eccentric connectivity index (ECI) of G is defined as ξ c (G) = ∑ v ∈ V G ε (v) d G (v) , where ε (v) , d G (v) and d G (u , v) are the eccentricity of v , the degree of v and the distance between u and v in G , respectively. In this paper, some extremal problems on the EDS and the ECI of graphs with given parameters are considered. Firstly, ordering the n -vertex graphs of diameter 2 with respect to the EDS (resp. the ECI) is established. Secondly, the sharp lower bound on the EDS of graphs with given minimum degree is determined. Moreover, the sharp upper bound on the ECI of graphs of diameter 2 with given minimum degree and the sharp lower bound on the ECI of cacti with given radius are established, respectively. Finally sharp upper and lower bounds on the difference between EDS and ECI among all n -vertex graphs of diameter 2 are determined. Thereafter the sharp lower bound on the difference between EDS and ECI among all n -vertex graphs of diameter 2 with given minimum degree (resp. connectivity, edge-connectivity and independence number) is determined. [ABSTRACT FROM AUTHOR]

Abstract The Kneser hypergraph KG n , k r is an r -uniform hypergraph with vertex set consisting of all k -subsets of { 1 , ... , n } and any collection of r vertices forms an edge if their corresponding k -sets are pairwise disjoint. The random Kneser hypergraph KG n , k r (p) is a spanning subhypergraph of KG n , k r in which each edge of KG n , k r is retained independently of each other with probability p. The independence number of random subgraphs of KG n , k 2 was recently addressed in a series of works by Bollobás et al. (2016), Balogh et al. (2015), Das and Tran (2016) and Devlin and Kahn (2016). It was proved that the random counterpart of the Erdős–Ko–Rado theorem continues to be valid even for very small values of p. In this paper, generalizing this result, we will investigate the independence number of random Kneser hypergraphs KG n , k r (p). Broadly speaking, when k is much smaller that n , we will prove that the random analogue of the Erdős matching conjecture is true even for extremely small values of p. [ABSTRACT FROM AUTHOR]

Abstract We determine the unique hypertrees with maximum spectral radius among k -uniform non-hyper-caterpillars with m edges and diameter d for 4 ≤ d ≤ m − 2 , among k -uniform non-hyper-caterpillars with m edges for m ≥ 6 , among k -uniform hypertrees with m edges and independence number α for ⌈ m (k − 1) + 1 k ⌉ ≤ α ≤ m , among k -uniform hypertrees with m edges and matching number β for 1 ≤ β ≤ ⌊ m (k − 1) + 1 k ⌋ , and among k -uniform hypertrees with m edges and s branch vertices for 0 ≤ s ≤ ⌊ m − 1 2 ⌋ , respectively. [ABSTRACT FROM AUTHOR]

The eccentric distance sum (EDS) of a connected graph G is defined as ξ d ( G ) = ∑ { u , v } ⊆ V G ( ε G ( u ) + ε G ( v ) ) d G ( u , v ) , where ε G ( ⋅ ) is the eccentricity of the corresponding vertex and d G ( u , v ) is the distance between u and v in G . In this paper, some extremal problems on the EDS of an n -vertex graph with respect to other two graph parameters are studied. Firstly, k -connected (bipartite) graphs with given diameter having the minimum EDS are characterized. Secondly, sharp lower bound on the EDS of connected graphs with given connectivity and minimum degree is determined. Lastly sharp lower bound on the EDS of connected graphs with given connectivity and independence number is determined as well. [ABSTRACT FROM AUTHOR]

This paper is devoted to the study of the graph sequence G n = ( V n , E n ) , where V n is the set of all vectors v ∈ R n with coordinates in { − 1 , 0 , 1 } such that | v | = 3 and E n consists of all pairs of vertices with scalar product 1. We find the exact value of the independence number of G n . As a corollary we get new lower bounds on χ ( R n ) and χ ( Q n ) for small values of n . [ABSTRACT FROM AUTHOR]

• Obtain that if α (G) ≤ k + ⌈ k + 1 r − 3 ⌉ − ⌊ 1 | r − k − 3 | + 1 ⌋ with k ≥ 2 and r ≥ 4 , then every 2-connected K 1 , r -free graph G contains a spanning tree with at most k leaves and the upper bound of α (G) is best possible. • Prove that if a connected K 1 , 4 -free graph G satisfies that α (G) ≤ 2 k + 5 , then G contains either a spanning tree with at most k branch vertices or a block B with α (B) ≤ 2. • Pose a related conjecture for 2-connected claw-free graphs. A vertex with degree one and a vertex with degree at least three are called a leaf and a branch vertex in a tree, respectively. In this paper, we obtain that every 2-connected K 1 , r -free graph G contains a spanning tree with at most k leaves if α (G) ≤ k + ⌈ k + 1 r − 3 ⌉ − ⌊ 1 | r − k − 3 | + 1 ⌋ , where k ≥ 2 and r ≥ 4. The upper bound is best possible. Furthermore, we prove that if a connected K 1 , 4 -free graph G satisfies that α (G) ≤ 2 k + 5 , then G contains either a spanning tree with at most k branch vertices or a block B with α (B) ≤ 2. A related conjecture for 2-connected claw-free graphs is also posed. [ABSTRACT FROM AUTHOR]

Let G = ( V ( G ) , E ( G ) ) be an ( n , m ) -graph. The Randić spread of G , s R ( G ) , is defined as the maximum distance of its Randić eigenvalues, disregarding the Randić spectral radius of G . In this work, we use numerical inequalities and bounds for the matricial spread to obtain relations between this spectral parameter and some structural and algebraic parameters of the underlying graph such as, the sequence of vertex degrees, the nullity, Randić index, generalized Randić indices and its independence number. In the last section a comparison is presented for regular graphs. [ABSTRACT FROM AUTHOR]

As a fundamental subject of theoretical computer science, the maximum independent set (MIS) problem not only is of purely theoretical interest, but also has found wide applications in various fields. However, for a general graph determining the size of a MIS is NP-hard, and exact computation of the number of all MISs is even more difficult. It is thus of significant interest to seek special graphs for which the MIS problem can be exactly solved. In this paper, we address the MIS problem in the pseudofractal scale-free web and the Sierpiński gasket, which have the same number of vertices and edges. For both graphs, we determine exactly the independence number and the number of all possible MISs. The independence number of the pseudofractal scale-free web is as twice as the one of the Sierpiński gasket. Moreover, the pseudofractal scale-free web has a unique MIS, while the number of MISs in the Sierpiński gasket grows exponentially with the number of vertices. [ABSTRACT FROM AUTHOR]

Let T be a tree. We show that the null space of the adjacency matrix of T has relevant information about the structure of T . We introduce the Null Decomposition of trees, which is a decomposition into two different types of trees: N-trees and S-trees. N-trees are the trees that have a unique maximum (perfect) matching. S-trees are the trees with a unique maximum independent set. We obtain formulas for the independence number and the matching number of a tree using this decomposition. We also show how the number of maximum matchings and the number of maximum independent sets in a tree are related to its null decomposition. [ABSTRACT FROM AUTHOR]

In this paper, we give some bounds on the signless Laplacian index of graphs in terms of independence number. In addition, these results disprove a conjecture in [3] involving the signless Laplacian index and independence number of graphs. [ABSTRACT FROM AUTHOR]

Tutte’s 3 -flow conjecture states that every 4 -edge-connected graph admits a nowhere-zero 3 -flow. In this paper, we characterize all graphs with independence number at most 4 that admit a nowhere-zero 3 -flow. The characterization of 3 -flow verifies Tutte’s 3 -flow conjecture for graphs with independence number at most 4 and with order at least 21 . In addition, we prove that every odd- 5 -edge-connected graph with independence number at most 3 admits a nowhere-zero 3 -flow. To obtain these results, we introduce a new reduction method to handle odd wheels. [ABSTRACT FROM AUTHOR]

The distance spectral radius of a graph is the largest eigenvalue of its distance matrix. X.L. Zhang (2012) [31] determined the n -vertex graphs of given diameter with the minimum distance spectral radius. In this paper, we generalize this result by characterizing the graphs of order n with given connectivity and diameter having minimum distance spectral radius. In addition, we determine the minimum distance spectral radius of graphs among the n -vertex graphs with given connectivity and independence number, and characterize the corresponding extremal graph, thus determining the minimum distance spectral radius of graphs among n -vertex graphs with given connectivity (resp. independence) number. [ABSTRACT FROM AUTHOR]

We study relationships between the diameter D (G) , the domination number γ (G) , the independence number α (G) and the cop number c (G) of a connected graph G , showing (i.) c (G) ≤ α (G) − ⌊ D (G) − 3 2 ⌋ , and (ii.) c (G) ≤ γ (G) − D (G) 3 + O (D (G)). [ABSTRACT FROM AUTHOR]

We investigate the bilinear forms graph Γ over the residue class ring modulo p s (where p is a prime number and s is a positive integer). First, we prove that the bilinear forms graph Γ is a connected vertex transitive graph. When p > 2 , Γ is distance-regular if and only if s = 1 . Next, we completely determine the valency of a vertex, the clique number, the independence number and the chromatic number of the bilinear forms graph Γ, respectively. Finally, we show that both Γ and the complement of Γ are not cores and their cores are complete. [ABSTRACT FROM AUTHOR]

Line graphs constitute a rich and well-studied class of graphs. In this paper, we focus on three different topics related to line graphs of subcubic triangle-free graphs. First, we show that any such graph G has an independent set of size at least 3 | V ( G ) | ∕ 10 , the bound being sharp. As an immediate consequence, we have that any subcubic triangle-free graph G , with n i vertices of degree i , has a matching of size at least 3 n 1 ∕ 20 + 3 n 2 ∕ 10 + 9 n 3 ∕ 20 . Then we provide several approximate min-max theorems relating cycle-transversals and cycle-packings of line graphs of subcubic triangle-free graphs. This enables us to prove Jones’ Conjecture for claw-free graphs with maximum degree 4 . Finally, we concentrate on the computational complexity of Feedback Vertex Set , Hamiltonian Cycle and Hamiltonian Path for subclasses of line graphs of subcubic triangle-free graphs. [ABSTRACT FROM AUTHOR]

A total dominating set of a graph G having non empty intersection with all the independent sets of maximum cardinality in G is an independent transversal total dominating set. The minimum cardinality of any independent transversal total dominating set is denoted by γ t t ( G ) . In this paper we introduce this concept and begin the study of its mathematical properties. Specifically, we prove that the complexity of the decision problem associated to the computation of the value of γ t t ( G ) is NP-complete, under the assumption that the independence number is known. Moreover, we present tight lower and upper bounds on γ t t ( G ) and give some realizability results in concordance with these bounds. For instance, we show that for any two positive integers a , b such that 2 ≤ a ≤ 2 b 3 there is a graph G of order b such that γ t t ( G ) = a . [ABSTRACT FROM AUTHOR]

Let α ( G ) , α ′ ( G ) , κ ( G ) and κ ′ ( G ) denote the independence number, the matching number, connectivity and edge connectivity of a graph G , respectively. We determine the finite graph families F 1 and F 2 such that each of the following holds. (i) If a connected graph G satisfies κ ′ ( G ) ≥ α ( G ) − 1 , then G has a spanning closed trail if and only if G is not contractible to a member of F 1 . (ii) If κ ′ ( G ) ≥ max { 2 , α ( G ) − 3 } , then G has a spanning trail. This result is best possible. (iii) If a connected graph G satisfies κ ′ ( G ) ≥ 3 and α ′ ( G ) ≤ 7 , then G has a spanning closed trail if and only if G is not contractible to a member of F 2 . [ABSTRACT FROM AUTHOR]

We show that for any graph G , by considering “activation” through the strong product with another graph H , the relation α ( G ) ≤ ϑ ( G ) between the independence number and the Lovász number of G can be made arbitrarily tight: Precisely, the inequality α ( G ⊠ H ) ⩽ ϑ ( G ⊠ H ) = ϑ ( G ) ϑ ( H ) becomes asymptotically an equality for a suitable sequence of ancillary graphs H . This motivates us to look for other products of graph parameters of G and H on the right hand side of the above relation. For instance, a result of Rosenfeld and Hales states that α ( G ⊠ H ) ⩽ α ∗ ( G ) α ( H ) , with the fractional packing number α ∗ ( G ) , and for every G there exists H that makes the above an equality; conversely, for every graph H there is a G that attains equality. These findings constitute some sort of duality of graph parameters, mediated through the independence number, under which α and α ∗ are dual to each other, and the Lovász number ϑ is self-dual. We also show duality of Schrijver’s and Szegedy’s variants ϑ − and ϑ + of the Lovász number, and explore analogous notions for the chromatic number under strong and disjunctive graph products. [ABSTRACT FROM AUTHOR]

The atom-bond connectivity (ABC) index is a degree-based topological index. It was introduced due to its applications in modeling the properties of certain molecular structures and has been since extensively studied. In this note, we examine the influence on the extremal values of the ABC index by various graph parameters. More specifically, we consider the maximum ABC index of connected graphs of given order, with fixed independence number, number of pendent vertices, chromatic number and edge-connectivity respectively. We provide characterizations of extremal structures as well as some conjectures. Numerical analysis of the extremal values is also presented. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a connected graph with vertex set V ( G ) = { v 1 , v 2 , … , v n } and edge set E ( G ) . The transmission Tr ( v i ) of vertex v i is defined to be the sum of distances from v i to all other vertices. Let Tr ( G ) be the n × n diagonal matrix with its ( i , i ) -entry equal to Tr G ( v i ) . The distance signless Laplacian is defined as D Q ( G ) = Tr ( G ) + D ( G ) , where D ( G ) is the distance matrix of G . Let ∂ 1 ( G ) ≥ ∂ 2 ( G ) ≥ ⋯ ≥ ∂ n ( G ) denote the eigenvalues of distance signless Laplacian matrix of G . In this paper, we first characterize all graphs with ∂ n ( G ) = n − 2 . Secondly, we characterize all graphs with ∂ 2 ( G ) ∈ [ n − 2 , n ] when n ≥ 11 . Furthermore, we give the lower bound on ∂ 2 ( G ) with independence number α and the extremal graph is also characterized. [ABSTRACT FROM AUTHOR]

Rivera-Campo provided a degree sum condition for a graph to have a spanning tree with bounded degrees and leaves. In this paper, we give an independence number condition for a graph to have a spanning tree with bounded degrees and leaves, which also partially solves the conjecture made by Enomoto and Ozeki (2010). [ABSTRACT FROM AUTHOR]

The Wiener polarity index W p ( G ) of a graph G is the number of unordered pairs of vertices { u ,  v } in G such that the distance between u and v is equal to 3. Very recently, Zhang and Hu studied the Wiener polarity index in [Y. Zhang, Y. Hu, 2016] [38]. In this short paper, we establish an upper bound on the Wiener polarity index in terms of Hosoya index and characterize the corresponding extremal graphs. Moreover, we obtain Nordhaus–Gaddum-type results for W p ( G ). Our lower bound on W p ( G ) + W p ( G ¯ ) is always better than the previous lower bound given by Zhang and Hu. [ABSTRACT FROM AUTHOR]