Search

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.

Let G be a graph and I be an interval. In this paper, we present bounds for the number m G I of Laplacian eigenvalues in I in terms of structural parameters of G. In particular, we show that m G ( n − α ( G ) , n ] ≤ n − α ( G ) and m G ( n − d ( G ) + 3 , n ] ≤ n − d ( G ) − 1 , where α ( G ) and d ( G ) denote the independence number and the diameter of G, respectively. Also, we characterize bipartite graphs that satisfy m G [ 0 , 1 ) = α ( G ) . Further, in the case of triangle-free or quadrangle-free, we prove that m G ( n − 1 , n ] ≤ 1 .

Let D be a digraph and let α ( D ) , α ′ ( D ) and λ ( D ) be independence number, the matching number and the arc-strong connectivity of D , respectively. Bang-Jensen and Thommasse in 2011 conjectured that every digraph D with λ ( D ) ≥ α ( D ) is supereulerian. In [J. Graph Theory, 81(4), (2016) 393-402], it is shown that every digraph D with λ ( D ) ≥ α ′ ( D ) is supereulerian. In this paper, we introduced the symmetric core of a digraph and use it to show that each of the following holds for a strong digraph D on n ≥ 3 vertices with λ ( D ) ≥ α ′ ( D ) − 1 . ( i ) There exists a family D ( n ) of well-characterized digraphs such that for any digraph D with α ′ ( D ) ≤ 2 , D has a spanning trial if and only if D is not a member in D ( n ) . ( i i ) If α ′ ( D ) ≥ 3 , then D has a spanning trail. ( i i i ) If α ′ ( D ) ≥ 3 and n ≥ 2 α ′ ( D ) + 3 , then D is supereulerian. ( i v ) If λ ( D ) ≥ α ′ ( D ) ≥ 4 and n ≥ 2 α ′ ( D ) + 3 , then for any pair of vertices u and v of D , D contains a spanning ( u , v ) -trail.

In this note, we disprove two conjectures on no hole anti- n -labeling of graphs proposed by Guan et al. (2019), and characterize a graph G with λ n n h ( G ) = α ( G ) , where λ n n h ( G ) and α ( G ) denote the no hole anti- n -labeling number and the independence number of G , respectively.

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.

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.

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 , α ) .

In this work we study the null space of bipartite graphs without cycles of length 0 modulo 4 (denoted as C 4 k -free bipartite graphs), and its relation to structural properties. We extend the Null Decomposition of trees, introduced by Jaume and Molina (2018), to C 4 k -free bipartite graphs. This decomposition uses the null space of the adjacency matrix of a graph G to decompose it into two different types of graphs: C N ( G ) and C S ( G ) . C N has perfect matching number. C S ( G ) has a unique maximum independent set. We obtain formulas for the independence number and the matching number of a C 4 k -free bipartite graph using this decomposition. We also show how the number of maximum matchings and the number of maximum independent sets in a C 4 k -free bipartite graph are related to its null decomposition.

Let D be a symmetric ( v , k , λ ) design and Γ be its incidence graph. This paper focuses on the metric dimension and metric independence number of the incidence graphs of symmetric designs, along with their fractional versions. It proves that both the fractional metric dimension and the fractional metric independence number of Γ are v k + 1 − λ , which induces the lower or upper bounds on the metric dimension and metric independence number of Γ . In particular, it determines the metric dimension number or metric independence number, and their basis, of finite projective planes, finite biplanes, and trivial symmetric designs.

Graphs with few distinct eigenvalues have been investigated extensively. In this paper, we focus on a related problem: characterizing graphs with some eigenvalue of large multiplicity. Specifically, the normalized Laplacian matrix of a graph is considered here. Let ρ n − 1 ( G ) and ν ( G ) be the second smallest normalized Laplacian eigenvalue and the independence number of a graph G, respectively. As the main conclusions, two families of n-vertex connected graphs with some normalized Laplacian eigenvalue of multiplicity n − 3 are determined: graphs with ρ n − 1 ( G ) = 1 and graphs with ρ n − 1 ( G ) ≠ 1 and ν ( G ) = 3 . Moreover, it is proved that these graphs are determined by their normalized Laplacian spectrum.

We obtain new upper and lower bounds for the independence number and the chromatic number of generalized preferential attachment graphs.

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.

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–Lovasz 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–Lovasz 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 .

Let G be a graph and P be a class of graphs. We consider list colouring of vertices of G in which the sizes of lists assigned to different vertices can be different. We colour G from the lists in such a way that vertices of each colour class induce a graph in P . The smallest possible sum of all the list sizes, such that, according to the rules, G is colourable for any particular assignment of the lists of these sizes is denoted by χ s c P ( G ) . Let D 1 , I 1 be classes of acyclic and triangle-free graphs, respectively. Given a graph G , we consider a graph H G whose vertex set is the set of triangles of G and whose two vertices t 1 , t 2 are adjacent if the triangles t 1 , t 2 share an edge in G . In this work we provide an upper bound of n + α ( H G ) on χ s c D 1 ( G ) , where G is an arbitrary n -vertex 2-tree and α ( H G ) is the independence number of H G . We give a polynomial-time algorithm to find the assignment of list sizes that realizes this bound. Moreover, we prove that this bound is achieved for an arbitrary n -vertex 2-tree G that is 3-sun-free (equivalently, Hajoś-graph-free, see Fig. 7) and for such an n -vertex 2-tree G whose graph H G is a tree with α ( H G ) = ⌈ n 2 ⌉ − 1 . Finally, we show that χ s c I 1 ( G ) = χ s c D 1 ( G ) for each 2-tree G .

The analogue of Hadwiger's conjecture for the immersion order, a conjecture independently posed by Lescure and Meyniel, and by Abu-Khzam and Langston, states that every graph G which does not contain the complete graph Kt+1 as an immersion satisfies χ(G) ≤ t. If true, this conjecture would imply that every graph with n vertices and independence number α contains K ⌈ n α ⌉ as an immersion (and if α = 2, the two statements are known to be equivalent). The immersion conjecture has been tackled with more success than its graph minors counterpart: not only is a linear upper bound known for the chromatic number of Kt+1-immersion-free graphs, but the best bound currently known is very close to optimal. Namely, the currently best bound in this respect is due to Gauthier, Le and Wollan, who recently proved that every graph not containing Kt+1 as an immersion satisfies χ(G) ≤ 3.54t + 7. Their result implies that any graph with n vertices and independence number α contains K ⌈ n 3.54 α − c ⌉ as an immersion, where c K 2 ⌊ n 5 ⌋ as an immersion. We show that any graph with n vertices and independence number 3 contains a clique immersion on at least ⌊ 2 n 9 ⌋ − 1 vertices, and any graph with n vertices and independence number 4 contains a clique immersion on at least ⌊ 4 n 27 ⌋ − 1 vertices. Thus, comparing to the bound from above, in both cases we roughly double the size of the immersion obtained.

The famous lower bound α ( G ) ≥ ∑ u ∈ V ( G ) 1 d G ( u ) + 1 on the independence number α ( G ) of a graph G due to Caro and Wei is known to be satisfied with equality if and only if the components of G are cliques. The bound has been generalized in the context of large degenerate subsets and small dynamic monopolies, and we extend Selkow’s strengthening of it in this way. Furthermore, we give a simple proof of a bound concerning partial incentives due to Cordasco, Gargano, Rescigno, and Vaccaro. Finally, we characterize the extremal graphs for these bounds as well as for a recent lower bound on the independence number due to Angel, Campigotto, and Laforest.

This article studies the k -forcing number for oriented graphs, generalizing both the zero forcing number for directed graphs and the k -forcing number for simple graphs. In particular, given a simple graph G , we introduce the maximum (minimum) oriented k -forcing number, denoted MOF k ( G ) ( mof k ( G ) ), which is the largest (smallest) k -forcing number among all possible orientations of G . These new ideas are compared to known graph invariants and it is shown that, among other things, mof ( G ) equals the path covering number of G while MOF k ( G ) is greater than or equal to the independence number of G — with equality holding if G is a tree or if k is at least the maximum degree of G . Along the way, we also show that many recent results about k -forcing number can be modified for oriented graphs.

Considering connected K 1 , 3 -free graphs with independence number at least 3, Chudnovsky and Seymour (2010) showed that every such graph, say G , is 2 ω -colourable where ω denotes the clique number of G . We study ( K 1 , 3 , Y ) -free graphs, and show that the following three statements are equivalent. • [(1)] Every connected ( K 1 , 3 , Y ) -free graph which is distinct from an odd cycle and which has independence number at least 3 is perfect. • [(2)] Every connected ( K 1 , 3 , Y ) -free graph which is distinct from an odd cycle and which has independence number at least 3 is ω -colourable. • [(3)] Y is isomorphic to an induced subgraph of P 5 or Z 2 (where Z 2 is also known as hammer). Furthermore, for connected ( K 1 , 3 , Y ) -free graphs (without an assumption on the independence number), we show a similar characterisation featuring the graphs P 4 and Z 1 (where Z 1 is also known as paw).

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.

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 l -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 l -independence number, and give the exact value of the independence number of the Cartesian square of K ( k s + 1 , k ) s − stab .

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 Bollobas 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 .

The transversal number τ ( G ) of a hypergraph G is the minimum cardinality of a set of vertices that intersects all edges of G . For r ≥ 1 define f r = sup τ ( G ) | V ( G ) | + | E ( G ) | , where G ranges over all r -uniform hypergraphs. In 1990 Alon proved that f r = ( 1 + o ( 1 ) ) ln r r . We consider the following generalization of this problem. Given an r -uniform hypergraph H , the H -transversal number τ H ( G ) of a hypergraph G is the minimum cardinality of a set of vertices that intersects the vertex set of every copy of H in G . Define f r ( H ) = sup τ H ( G ) | V ( G ) | + | E ( G ) | , where G ranges over all r -uniform hypergraphs. We prove that f 2 ( K q ) = 1 2 q − 1 , f 2 ( P 3 ) = 1 ∕ 4 , f 2 ( P 4 ) = 1 ∕ 5 , f 2 ( C 4 ) = 1 ∕ 6 , and 1 5 2 q + 1 ≤ f 2 ( C q ) ≤ f 2 ( P q ) ≤ 1 ∕ 5 for q ≥ 5 . In order to prove these results we establish a connection between H -transversals and the node-fault-tolerance in graphs. Furthermore, we derive some bounds on the H -independence number.

A graph G is called a pseudo-core if every endomorphism of G is either an automorphism or a colouring. A graph G is a core if every endomorphism of G is an automorphism. Let F q be the finite field with q elements where q is a power of an odd prime number. The quadratic forms graph, denoted by Quad ( n , q ) where n ≥ 2 , has all quadratic forms on F q n as vertices and two vertices f and g are adjacent whenever rk ( f − g ) = 1 or 2. We prove that every Quad ( n , q ) is a pseudo-core. Further, when n is even, Quad ( n , q ) is a core. When n is odd, Quad ( n , q ) is not a core. On the other hand, we completely determine the independence number of Quad ( n , q ) .

This paper is concerned with the recently introduced Sombor index S O , defined as S O = S O ( G ) = ∑ v k v l ∈ E ( G ) d G ( v k ) 2 + d G ( v l ) 2 , where d G ( v ) is the degree of the vertex v of a graph G . We present bounds on S O of trees in terms of order, independence number, and number of pendent vertices, and characterize the extremal cases. In addition, analogous results for quasi-trees are established.

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.

The eccentric distance sum (EDS) of a connected graph G is defined as ξ d ( G ) = ∑ { u , v } ⊆ V G ( e G ( u ) + e G ( v ) ) d G ( u , v ) , where e 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.

A 2-partition of a digraph D is a partition ( V 1 , V 2 ) of V ( D ) into two disjoint non-empty sets V 1 and V 2 such that V 1 ∪ V 2 = V ( D ) . A semicomplete digraph is a digraph with no pair of non-adjacent vertices. We consider the complexity of deciding whether a given semicomplete digraph has a 2-partition such that each part of the partition induces a (semicomplete) digraph with some specified property. In [4] and [5] Bang-Jensen, Cohen and Havet determined the complexity of 120 such 2-partition problems for general digraphs. Several of these problems are NP-complete for general digraphs and thus it is natural to ask whether this is still the case for well-structured classes of digraphs, such as semicomplete digraphs. This is the main topic of the paper. More specifically, we consider 2-partition problems where the set of properties are minimum out-, minimum in- or minimum semi-degree. Among other results we prove the following: • For all integers k 1 , k 2 ≥ 1 and k 1 + k 2 ≥ 3 it is NP-complete to decide whether a given digraph D has a 2-partition ( V 1 , V 2 ) such that D 〈 V i 〉 has out-degree at least k i for i = 1 , 2 . • For every fixed choice of integers α , k 1 , k 2 ≥ 1 there exists a polynomial algorithm for deciding whether a given digraph of independence number at most α has a 2-partition ( V 1 , V 2 ) such that D 〈 V i 〉 has out-degree at least k i for i = 1 , 2 . • For every fixed integer k ≥ 1 there exists a polynomial algorithm for deciding whether a given semicomplete digraph has a 2-partition ( V 1 , V 2 ) such that D 〈 V 1 〉 has out-degree at least one and D 〈 V 2 〉 has in-degree at least k. • It is NP-complete to decide whether a given semicomplete digraph D has a 2-partition ( V 1 , V 2 ) such that D 〈 V i 〉 is a strong tournament.

A mod ( 2 p + 1 ) -orientation D is an orientation of G such that d D + ( v ) ≡ d D − ( v ) ( mod 2 p + 1 ) for any vertex v ∈ V ( G ) . Extending Tutte’s integer flow conjectures, it was conjectured by Jaeger that every 4 p -edge-connected graph has a mod ( 2 p + 1 ) -orientation. However, this conjecture has been disproved in Han et al. (2018) recently. Infinite families of 4 p -edge-connected graphs (for p ≥ 3 ) and ( 4 p + 1 ) -edge-connected graphs (for p ≥ 5 ) with no mod ( 2 p + 1 ) -orientation are constructed in Han et al. (2018). In this paper, we show that every family of graphs with bounded independence number has only finitely many contraction obstacles for admitting mod ( 2 p + 1 ) -orientations, contrasting to those infinite families. More precisely, we prove that for any integer t ≥ 2 , there exists a finite family F = F ( p , t ) of graphs that do not have a mod ( 2 p + 1 ) -orientation, such that every graph G with independence number at most t either admits a mod ( 2 p + 1 ) -orientation or is contractible to a member in F . This indicates that the problem of determining whether every k -edge-connected graph with independence number at most t admits a mod ( 2 p + 1 ) -orientation is computationally solvable for fixed k and t . In particular, the graph family F ( p , 2 ) is determined, and our results imply that every 8-edge-connected graph G with independence number at most two admits a mod 5-orientation.

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 .

The inverse sum indeg index, which was selected in Vukicevic (2010) [14] as a significant predictor of total surface area of octane isomers and for which the extremal graphs obtained with the help of MathChem have a particularly simple and elegant structure, is defined as ISI ( G ) = ∑ u v ∈ E ( G ) d u d v d u + d v , where d u is the degree of the vertex u of G. Recently, Falahati-Nezhad, Azari and Doslic (2017) [3] gave several sharp upper and lower bounds on this index in terms of some molecular structural parameters such as the order, size, radius, number of pendant vertices, minimal and maximal vertex degrees, and minimal non-pendent vertex degree, and related this index to several well-known molecular descriptors. In this paper, we present sharp bounds for the inverse sum indeg index for graphs with given matching number, independence number and vertex-connectivity, and we also characterize all extremal graphs for which those bounds are obtained.

Let $G$ be a finite simple graph. For $X \subset V(G)$, the difference of $X$, $d(X) := |X| - |N (X)|$ where $N(X)$ is the neighborhood of $X$ and $\max \, \{d(X):X\subset V(G)\}$ is called the critical difference of $G$. $X$ is called a critical set if $d(X)$ equals the critical difference and ker$(G)$ is the intersection of all critical sets. It is known that ker$(G)$ is an independent (vertex) set of $G$. diadem$(G)$ is the union of all critical independent sets. An independent set $S$ is an inclusion minimal set with $d(S) > 0$ if no proper subset of $S$ has positive difference. A graph $G$ is called K\"onig-Egerv\'ary if the sum of its independence number ($\alpha (G)$) and matching number ($\mu (G)$) equals $|V(G)|$. It is known that bipartite graphs are K\"onig-Egerv\'ary. In this paper, we study independent sets with positive difference for which every proper subset has a smaller difference and prove a result conjectured by Levit and Mandrescu in 2013. The conjecture states that for any graph, the number of inclusion minimal sets $S$ with $d(S) > 0$ is at least the critical difference of the graph. We also give a short proof of the inequality $|$ker$(G)| + |$diadem$(G)| \le 2\alpha (G)$ (proved by Short in 2016). A characterization of unicyclic non-K\"onig-Egerv\'ary graphs is also presented and a conjecture which states that for such a graph $G$, the critical difference equals $\alpha (G) - \mu (G)$, is proved. We also make an observation about ker$G)$ using Edmonds-Gallai Structure Theorem as a concluding remark., Comment: 18 pages, 2 figures

A set S ⊆ V ( G ) is a k -independent set of a graph G if the distance between every two vertices of S is greater than k . The k -independence number α k ( G ) of G is the maximum cardinality over all k -independent set in G . In this note, we show that if G is a t -connected graph of order n , then α 2 k + 1 ( G ) ≤ max { 1 , n − t t k + 1 } and α 2 k ( G ) ≤ max { 1 , n t k + 1 } for any integer k ≥ 0 . Both bounds are sharp. For any integer s ≥ 2 , p ( G , s ) = max { min 1 ≤ i ≤ j ≤ s d ( v i , v j ) : { v 1 , … , v s } ⊆ V ( G ) } , is a generalization of the diameter of G . We determine the exact value of the maximum p ( G , s ) among all t -connected graphs of order n . This includes the main results of a recent paper by Knor and Skrekovski (On the minimum distance in a k -vertex set in a graph, Appl. Math. Comput. 356 (2019) 99–104) and solve an open problem therein.

We investigate the generalized bilinear forms graph Γ d over a residue class ring Z p s . The graph Γ d is a connected vertex-transitive graph, and we completely determine its independence number, clique number, chromatic number and maximum cliques. We also prove that cores of both Γ d and its complement are maximum cliques. The graph Γ d is useful for error-correcting codes. We show that there is a largest independent set of Γ d which is a linear MRD code over Z p s .

Let $G=\left( \mathcal{V}\left( G\right) ,\mathcal{E}\left( G\right) \right) $ be an $\left( n,m\right) $-graph. The Randi\'{c} spread of $G$, $s_{R}(G)$, is defined as the maximum distance of its Randi\'{c} eigenvalues, disregarding the Randi\'{c} 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\'{c} index, generalized Randi\'{c} indices and its independence number. In the last section a comparison is presented for regular graphs.

Let G be a graph on n vertices with independence number α . We prove that if n is sufficiently large ( n ≥ α 2 k + 1 will do), then G always contains a k -connected subgraph on at least n ∕ α vertices. The value of n ∕ α is sharp, since G might be the disjoint union of α equally-sized cliques. For k ≥ 3 and α = 2 , 3 , we shall prove that the same result holds for n ≥ 4 ( k − 1 ) and n ≥ 27 ( k − 1 ) 4 respectively, and that these lower bounds on n are sharp.

The power graph Γ G of a finite group G is the graph whose vertex set is G , two distinct elements being adjacent if one is a power of the other. In this paper, we give sharp lower and upper bounds for the independence number of Γ G and characterize the groups achieving the bounds. Moreover, we determine the independence number of Γ G if G is cyclic, dihedral or generalized quaternion. Finally, we classify all finite groups G whose power graphs have independence number 3 or n − 2 , where n is the order of G .

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\'nski 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\'nski gasket. Moreover, the pseudofractal scale-free web has a unique MIS, while the number of MISs in the Sierpi\'nski gasket grows exponentially with the number of vertices., Comment: 15 pages, 10 figures

The slow-coloring game is played by Lister and Painter on a graph G . On each round, Lister marks a nonempty subset M of the uncolored vertices, scoring M points. Painter then gives a color to a subset of M that is independent in G . The game ends when all vertices are colored. Painter and Lister want to minimize and maximize the total score, respectively. The best score that each player can guarantee is the sum-color cost of G , written s ( G ) . The game is an online variant of online sum list coloring. We prove V ( G ) 2 α ( G ) + 1 2 ≤ s ( G ) V ( G ) ≤ max V ( H ) α ( H ) : H ⊂ G , where α ( G ) is the independence number, and we study when equality holds in the bounds. We compute s ( G ) for graphs with α ( G ) = 2 . Among n -vertex trees, we prove that s is minimized by the star and maximized by the path. We also study s ( K r , s ) .

For an $r$-uniform hypergraph $H$, let $f(H)$ be the minimum number of complete $r$-partite $r$-uniform subhypergraphs of $H$ whose edge sets partition the edge set of $H$. For a graph $G$, $f(G)$ is the bipartition number of $G$ which was introduced by Graham and Pollak in 1971. In 1988, Erd\H{o}s conjectured that if $G \in G(n,1/2)$, then with high probability $f(G)=n-\alpha(G)$, where $\alpha(G)$ is the independence number of $G$. This conjecture and related problems have received a lot of attention recently. In this paper, we study the value of $f(H)$ for a typical $r$-uniform hypergraph $H$. More precisely, we prove that if $(\log n)^{2.001}/n \leq p \leq 1/2$ and $H \in H^{(r)}(n,p)$, then with high probability $f(H)=(1-\pi(K^{(r-1)}_r)+o(1))\binom{n}{r-1}$, where $\pi(K^{(r-1)}_r)$ is the Tur\'an density of $K^{(r-1)}_r$., Comment: corrected few typos. updated the reference

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.

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.

An edge-colored connected graph G is properly connected if between every pair of distinct vertices, there exists a path such that no two adjacent edges have the same color. Fujita (2019) introduced the optimal proper connection number pcopt(G) for a monochromatic connected graph G , to make a connected graph properly connected efficiently. More precisely, pcopt ( G ) is the smallest integer p + q when one converts a given monochromatic graph G into a properly connected graph by recoloring p edges with q colors. In this paper, we show that pcopt ( G ) has an upper bound in terms of the independence number α ( G ) . Namely, we prove that for a connected graph G , pcopt ( G ) ≤ 5 α ( G ) − 1 2 . Moreover, for the case α ( G ) ≤ 3 , we improve the upper bound to 4, which is tight.

A connected graph is called a bi-block graph if each of its blocks is a complete bipartite graph. Let B ( k , α ) be the class of bi-block graph on k vertices with given independence number α . It is easy to see that every bi-block graph is a bipartite graph. For a bipartite graph G on k vertices, the independence number α ( G ) satisfies ⌈ k 2 ⌉ ≤ α ( G ) ≤ k − 1 . In this article, we prove that the maximum spectral radius ρ ( G ) among all graphs G in B ( k , α ) , is uniquely attained for the complete bipartite graph K α , k − α .

The Lescure–Meyniel conjecture is the analogue of Hadwiger’s conjecture for the immersion order. It states that every graph G contains the complete graph K χ ( G ) as an immersion, and like its minor-order counterpart it is open even for graphs with independence number 2. We show that every graph G with independence number α ( G ) ≥ 2 and no hole of length between 4 and 2 α ( G ) satisfies this conjecture. In particular, every C 4 -free graph G with α ( G ) = 2 satisfies the Lescure–Meyniel conjecture. We give another generalisation of this corollary, as follows. Let G and H be graphs with independence number at most 2, such that | V ( H ) | ≤ 4 . If G is H -free, then G satisfies the Lescure–Meyniel conjecture.

In a graph G = ( V , E ) (not necessarily be connected) an independent set S ⊆ V is said to be an outer connected independent set if ω ( G − S ) ≤ ω ( G ) , where ω ( G ) is the number of components in G. The maximum cardinality of an outer connected independent set is called the outer connected independence number and it is denoted by I o c ( G ) . This concept was introduced in [I. Sahul Hamid, R. Gnanaprahasam, M. Fatima Mary Outer Connected Independence in Graphs, Discrete Math, Algorithm, Appl Vol. 7, No. 3 1550039 (2015) [11 pages] DOI]. This paper examine the effect of I o c when G is modified by deleting an edge.

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.

The leaf distance of a tree is the maximum d such that the distance between any pair of leaves in the tree is at least d. Kaneko provided sufficient conditions to force the existence of a spanning tree with leaf distance at least d=3 and conjectured that similar conditions suffice for larger d. The case when d=4 was later proved by Kaneko, Kano, and Suzuki. In this paper, we show that when d4, a stronger form of this conjecture holds for graphs with independence number at most five. As an immediate corollary, we obtain that when dn3, this stronger version holds for all n-vertex graphs, consequently proving Kanekos conjecture for dn3.

A bi-hole of size t in a bipartite graph G is a copy of K t , t in the bipartite complement of G . Given an n × n bipartite graph G , let β ( G ) be the largest k for which G has a bi-hole of size k . We prove that β ( G ) ≥ 1 2 ⋅ ∑ v ∈ V ( G ) 1 d ( v ) + 1 . Furthermore, we prove the following generalization of the result above. Given an n × n bipartite graph G , let β d ( G ) be the largest k for which G has a k × k induced d -degenerate subgraph. We prove that β d ( G ) ≥ 1 2 ⋅ ∑ v ∈ V ( G ) min 1 , d + 1 d ( v ) + 1 . Notice that β 0 ( G ) = β ( G ) .

For a given graph G, the Mostar index Mo(G) is the sum of absolute values of the differences between nu(e) and nv(e) over all edges e = u v of G, where nu(e) and nv(e) are, respectively, the number of vertices of G lying closer to u than to v and the number of vertices of G lying closer to v than to u. The degree sequence of a tree is the sequence of the degrees (in descending order) of the non-leaf vertices. This paper determines those trees with a given degree sequence which have the greatest Mostar index. Consequently, all extremal trees with the greatest Mostar index are obtained in the sets of all trees of order n with the maximum degree, the number of leaves, the independence number and the matching number, respectively. On the other hand, some properties of trees with a given degree sequence which have the least Mostar index are given. We also determine those trees with exactly n − 3 or n − 4 leaves when the degree sequence is given, which have the least Mostar index. At last some numerical results are discussed, in which we calculate the Mostar indices of two sets of molecular graphs: octane isomers and benzenoid hydrocarbons; We compare their Mostar indices with some other distance-based topological indices through their correlations with the chemical properties. The linear model for the Mostar index is better than or as good as the models corresponding to the other distance-based indices.

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 tt(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 tt(G) is NP-complete, under the assumption that the independence number is known. Moreover, we present tight lower and upper bounds on tt(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 2a2b3 there is a graph G of order b such that tt(G)=a.