Search

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

A subset S of vertices of a graph G is called a k -path vertex cover if every path of order k in G contains at least one vertex from S . Denote by ψ k ( G ) the minimum cardinality of a k -path vertex cover in G . In this article a lower and an upper bound for ψ k of the rooted product graphs are presented. Two characterizations are given when those bounds are attained. Moreover ψ 2 and ψ 3 are exactly determined. As a consequence the independence and the dissociation number of the rooted product are given. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph. The eccentric distance sum (EDS) of G is defined as ξ d ( G ) = ∑ v ∈ V ε G ( v ) D G ( v ) , where ε G ( v ) is the eccentricity of the vertex v and D G ( v ) = ∑ u ∈ V d G ( u , v ) is the sum of all distances from the vertex v . In this paper, the trees having the maximal EDS among n -vertex trees with maximum degree Δ and among those with domination number 3 are characterized. The trees having the maximal or minimal EDS among n -vertex trees with independence number α and the trees having the maximal EDS among n -vertex trees with matching number m are also determined. [ABSTRACT FROM AUTHOR]

In 1995, Brouwer proved that the toughness of a connected k-regular graph G is at least k/λ-2, where λ is the maximum absolute value of the non-trivial eigenvalues of G. Brouwer conjectured that one can improve this lower bound to k/λ-1 and that many graphs (especially graphs attaining equality in the Hoffman ratio bound for the independence number) have toughness equal to k/λ. In this paper, we improve Brouwer's spectral bound when the toughness is small and we determine the exact value of the toughness for many strongly regular graphs attaining equality in the Hoffman ratio bound such as Lattice graphs, Triangular graphs, complements of Triangular graphs and complements of point-graphs of generalized quadrangles. For all these graphs with the exception of the Petersen graph, we confirm Brouwer's intuition by showing that the toughness equals k/(-λmin), where λmin is the smallest eigenvalue of the adjacency matrix of the graph. [ABSTRACT FROM AUTHOR]

Abstract: Let be a simple connected graph of order with maximum degree and minimum degree , and eigenvalues . It is shown that the independence number of can be bounded from above by and . [Copyright &y& Elsevier]

Abstract: Sharp upper bounds on the average eccentricity of a connected graph of given order in terms of its independence number, chromatic number, domination number or connected domination number are given. Our results settle two conjectures of the computer program AutoGraphiX (Aouchiche et al., 2005). [Copyright &y& Elsevier]

Abstract: Let be a simple graph with vertex set and edge set . The rank of , written as , is defined to be the rank of its adjacency matrix. Let denote , where , and means the number of connected components of , and let respectively be the matching number, the independence number, and the chromatic index of . In this paper, it is proved that , , and . Examples are given to show that all the bounds can be attained. [Copyright &y& Elsevier]

Abstract: We introduce a natural generalization of an independent set of a graph and give a sharp lower bound on its size. The bound generalizes the widely known Caro and Wei result on the independence number of a graph. We use this result in the following problem. Given non-negative real numbers the cost of a graph is defined by . We estimate the minimum cost of a -vertex stable graph, i.e. a graph which contains a clique after removing any of its vertices. [Copyright &y& Elsevier]

Abstract: A pseudo -factor of a graph is a spanning subgraph in which each component on at least three vertices verifies , for every vertex in . Given an integer , we show that a graph with minimum degree , independence number and without isolated vertices possesses a pseudo -factor with at most components that are edges or vertices. This bound is sharp. [Copyright &y& Elsevier]

Abstract: We propose a new lower bound on the independence number of a graph. We show that our bound compares favorably to recent ones (e.g. Harant (2011) [12]). We obtain our bound by using the Bhatia–Davis inequality applied with analytical results (minimum, maximum, expectation and variance) of an algorithm for the vertex cover problem. [Copyright &y& Elsevier]

Abstract: A 2-hued coloring of a graph is a coloring such that, for every vertex of degree at least , the neighbors of receive at least two colors. The smallest integer such that has a 2-hued coloring with colors is called the 2-hued chromatic number of , and is denoted by . In this paper, we will show that, if is a regular graph, then , and, if is a graph and , then , and in the general case, if is a graph, then . [Copyright &y& Elsevier]

Abstract: A directed dominating set in a directed graph is a set of vertices of such that every vertex has an adjacent vertex in with directed to . The directed domination number of , denoted by , is the minimum cardinality of a directed dominating set in . The directed domination number of a graph , denoted by , is the maximum directed domination number over all orientations of . The directed domination number of a complete graph was first studied by Erdös [P. Erdös, On Schütte problem, Math. Gaz. 47 (1963) 220–222], albeit in disguised form. The authors [Y. Caro, M.A. Henning, A Greedy partition lemma for directed domination, Discrete Optim. 8 (2011) 452–458] recently extended this notion to directed domination of all graphs. In this paper we continue this study of directed domination in graphs. We show that the directed domination number of a bipartite graph is precisely its independence number. Several lower and upper bounds on the directed domination number are presented. [Copyright &y& Elsevier]

Abstract: An arc of a graph is an oriented edge and a 3-arc is a 4-tuple of vertices such that both and are paths of length two. The 3-arc graph of a graph is defined to have the arcs of as vertices such that two arcs are adjacent if and only if is a 3-arc of . In this paper, we study the independence, domination and chromatic numbers of 3-arc graphs and obtain sharp lower and upper bounds for them. We introduce a new notion of arc-coloring of a graph in studying vertex-colorings of 3-arc graphs. [ABSTRACT FROM AUTHOR]

Abstract: The complexity status of the Maximum Independent Set Problem (MIS) for the family of -free graphs is unknown. Although for many subclasses of -free graphs MIS can be solved in polynomial time, only exponential time MIS-algorithms for general graphs are known so far. In this note we present the first algorithm to solve MIS for -free graphs in subexponential time. [Copyright &y& Elsevier]

Abstract: We show that a graph with minimum degree , independence number and without isolated vertices, possesses a partition by vertex-disjoint cycles and at most edges or vertices. [Copyright &y& Elsevier]

Abstract: An offensive alliance in a graph is a set of vertices where for each vertex in its boundary the majority of vertices in ’s closed neighborhood are in . In the case of strong offensive alliance, strict majority is required. An alliance is called global if it affects every vertex in , that is, is a dominating set of . The global offensive alliance number is the minimum cardinality of a global offensive alliance in . An offensive alliance is connected if its induced subgraph is connected. The global-connected offensive alliance number, , is the minimum cardinality of a global-connected offensive alliance in . In this paper we obtain several tight bounds on and in terms of several parameters of . The case of strong alliances is studied by analogy. [Copyright &y& Elsevier]

Abstract: A set of vertices in a graph is independent if no neighbor of a vertex of belongs to . The independence number is the maximum cardinality of an independent set of . A series of best possible lower and upper bounds on and some other common invariants of are obtained by the system AGX 2, and proved either automatically or by hand. In the present paper, we report on such lower and upper bounds considering, as second invariant, minimum, average and maximum degree, diameter, radius, average distance, spread of eccentricities, chromatic number and matching number. [Copyright &y& Elsevier]

Abstract: A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality . Plummer [Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91–98] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. Every well-covered graph G without isolated vertices has a perfect -factor , i.e. a spanning subgraph such that each component is 1-regular or 2-regular. Here, we characterize all well-covered graphs G satisfying for some perfect -factor . This class contains all well-covered graphs G without isolated vertices of order n with , and in particular all very well-covered graphs. [Copyright &y& Elsevier]

An attempt of introducing a general notion of local transformation of a graph is made. The investigated notion is applied to the independent set problem. [Copyright &y& Elsevier]

The local independence number αi(G) of a graph G at a distance i is the maximum number of independent vertices at distance i from any vertex. We study the impact of restricting αi(G) on the (global) independence number α(G). Among others, we show that in graphs with bounded diameter, α(G) is bounded if and only if αi(G) is bounded for at least one i, 2⩽i⩽(diam(G)−1)/4. [Copyright &y& Elsevier]

Rotagraphs generalize all standard products of graphs in which one factor is a cycle. A computer-based approach for searching graph invariants on rotagraphs is proposed and two of its applications are presented. First, the λ-numbers of the Cartesian product of a cycle and a path are computed, where the λ-number of a graph G is the minimum number of colors needed in a (2,1)-coloring of G. The independence numbers of the family of the strong product graphs C7⊠C7⊠C2k+1 are also obtained. [Copyright &y& Elsevier]