Search

If α (G) + μ (G) = V , then G = V , E is a König–Egerváry graph, where α (G) denotes the cardinality of a maximum independent set, while μ (G) is the size of a maximum matching in G. If d 1 ≤ d 2 ≤ ⋯ ≤ d n is the degree sequence of G, then the annihilation number a G of G is the largest integer k such that ∑ i = 1 k d i ≤ E (Pepper, Binding independence, Ph.D. Dissertation, University of Houston, 2004; Pepper, On the annihilation number of a graph, in: Recent Advances in Electrical Engineering: Proceedings of the 15th American Conference on Applied Mathematics, pp 217–220, 2009). A set A ⊆ V satisfying ∑ a ∈ A d e g (a) ≤ E is an annihilation set; if, in addition, d e g v + ∑ a ∈ A d e g (a) > E , for every vertex v ∈ V (G) - A , then A is a maximal annihilation set in G. In Larson and Pepper (Graphs with equal independence and annihilation numbers. Electron J Comb 18:180, 2011) it was conjectured that the following assertions are equivalent: (i) α G = a G ; (ii)G is a König–Egerváry graph and every maximum independent set is a maximal annihilating set. Recently, it turned out that the implication “(i) ⟹ (ii)” was not true. A series of corresponding counterexamples can be found in Hiller (Counterexamples to the characterisation of graphs with equal independence and annihilation number. arXiv:2202.07529v1 [math.CO], 2022). In Levit and Mandrescu (On an annihilation number conjecture. Ars Math. Contemp. 18, 359–369, 2020), we presented an infinite family of non-bipartite König–Egerváry graphs that invalidate the “ (ii) ⟹ (i)” part of this conjecture. In this paper, we provide two more infinite families of counterexamples, one consisting of trees and the other one comprising non-tree bipartite graphs. We also show that the above conjecture is true for trees with α G = 4 , disconnected non-bipartite König–Egerváry graphs with α G = 4 , and disconnected bipartite graphs with α G = 4 excluding the three following counterexamples: C 4 ∪ 2 K 2 , D o m i n o ∪ K 2 and K 3 , 3 - e . [ABSTRACT FROM AUTHOR]

A graph is well-covered if all its maximal independent sets are of the same cardinality (Plummer in J Comb Theory 8:91-98, 1970). If G is a well-covered graph with at least two vertices, and $$G{-}v$$ is well-covered for every vertex v, then G is a 1- well-covered graph (Staples in On some subclasses of well-covered graphs. Ph.D. Thesis, Vanderbilt University, 1975). The graph G is $$\lambda $$ - quasi-regularizable if $$\lambda >0$$ and $$\lambda \cdot \vert S\vert \le \vert N( S) \vert $$ for every independent set S of G. It is known that every well-covered graph without isolated vertices is 1-quasi-regularizable (Berge in Ann Discret Math 12:31-44, 1982). The independence polynomial $$I(G;x)= {\sum _{k=0}^{\alpha }} s_{k}x^{k}$$ is the generating function of independent sets in a graph G (Gutman and Harary in Util Math 24:97-106, 1983), where $$\alpha $$ is the independence number of G. The Roller-Coaster Conjecture (Michael and Traves in Graphs Comb 19:403-411, 2003), saying that for every permutation $$\sigma $$ of the set $$\{\lceil \frac{\alpha }{2}\rceil ,\ldots ,\alpha \}$$ there exists a well-covered graph G with the independence number $$\alpha $$ such that the coefficients $$( s_{k}) $$ of I( G; x) satisfy has been validated in Cutler and Pebody (J Comb Theory A 145:25-35, 2017). In this paper we show that independence polynomials of $$\lambda $$ -quasi-regularizable graphs are partially unimodal. More precisely, the coefficients of an upper part of I( G; x) are in non-increasing order. Based on this finding, we prove that the unconstrained part of the independence sequence is: for well-covered graphs, and for 1-well-covered graphs, where $$\alpha $$ stands for the independence number, and n is the cardinality of the vertex set. [ABSTRACT FROM AUTHOR]

A graph is called unicyclic if it owns only one cycle. A matching M is called uniquely restricted in a graph G if it is the unique perfect matching of the subgraph induced by the vertices that M saturates. Clearly, μ( G) ≤ μ( G), where μ( G) denotes the size of a maximum uniquely restricted matching, while μ( G) equals the matching number of G. In this paper we study unicyclic bipartite graphs enjoying μ( G) = μ( G). In particular, we characterize unicyclic bipartite graphs having only uniquely restricted maximum matchings. Finally, we present some polynomial time algorithms recognizing unicyclic bipartite graphs with (only) uniquely restricted maximum matchings. [ABSTRACT FROM AUTHOR]

The independence number of a graph G, denoted by α( G), is the cardinality of a maximum independent set, and μ( G) is the size of a maximum matching in G. If α( G) + μ( G) equals its order, then G is a König-Egerváry graph. The square of a graph G is the graph G with the same vertex set as in G, and an edge of G is joining two distinct vertices, whenever the distance between them in G is at most two. G is a square-stable graph if it enjoys the property α( G) = α( G). In this paper we show that G is a König-Egerváry graph if and only if G is a square-stable König-Egerváry graph. [ABSTRACT FROM AUTHOR]

If by s is denoted the number of independent sets of cardinality k in a graph G, then $${I(G;x)=s_{0}+s_{1}x+\cdots+s_{\alpha}x^{\alpha}}$$ is the independence polynomial of G (Gutman and Harary in Utilitas Mathematica 24:97-106, ), where α = α( G) is the size of a maximum independent set. The inequality | I ( G; −1)| ≤ 2, where ν( G) is the cyclomatic number of G, is due to (Engström in Eur. J. Comb. 30:429-438, ) and (Levit and Mandrescu in Discret. Math. 311:1204-1206, ). For ν( G) ≤ 1 it means that $${I(G;-1)\in\{-2,-1,0,1,2\}.}$$ In this paper we prove that if G is a unicyclic well-covered graph different from C, then $${I(G;-1)\in\{-1,0,1\},}$$ while if G is a connected well-covered graph of girth ≥ 6, non-isomorphic to C or K (e.g., every well-covered tree ≠ K), then I ( G; −1) = 0. Further, we demonstrate that the bounds {−2, 2} are sharp for I ( G; −1), and investigate other values of I ( G; −1) belonging to the interval [−2, 2]. [ABSTRACT FROM AUTHOR]

A set S of vertices is independent or stable in a graph G, and we write S ∈ Ind ( G), if no two vertices from S are adjacent, and α( G) is the cardinality of an independent set of maximum size, while core( G) denotes the intersection of all maximum independent sets. G is called a König-Egerváry graph if its order equals α( G) + μ( G), where μ( G) denotes the size of a maximum matching. The number def ( G) = | V( G) | −2 μ( G) is the deficiency of G. The number $${d(G)=\max\{\left\vert S\right\vert -\left\vert N(S)\right\vert :S\in\mathrm{Ind}(G)\}}$$ is the critical difference of G. An independent set A is critical if $${\left\vert A\right\vert -\left\vert N(A)\right\vert =d(G)}$$ , where N( S) is the neighborhood of S, and α( G) denotes the maximum size of a critical independent set. Larson (Eur J Comb 32:294-300, ) demonstrated that G is a König-Egerváry graph if and only if there exists a maximum independent set that is also critical, i.e., α( G) = α( G). In this paper we prove that: (i) $${d(G)=\left \vert \mathrm{core}(G) \right \vert -\left \vert N (\mathrm{core}(G))\right\vert =\alpha(G)-\mu(G)=def \left(G\right)}$$ holds for every König-Egerváry graph G; (ii) G is König-Egerváry graph if and only if each maximum independent set of G is critical. [ABSTRACT FROM AUTHOR]

A stable set in a graph G is a set of pairwise non-adjacent vertices, and the stability number α( G) is the maximum size of a stable set in G. The independence polynomial of G is where s k equals the number of stable sets of cardinality k in G (Gutman and Harary [11]). Unlike the matching polynomial, the independence polynomial of a graph can have non-real roots. It is known that the polynomial I( G; x) has only real roots whenever (a) α( G) = 2 (Brown et al. [4]), (b) G is claw-free (Chudnowsky and Symour [6]). Brown et al. [3] proved that given a well-covered graph G, one can define a well-covered graph H such that G is a subgraph of H, α( G) = α( H), and I( H; x) has all its roots simple and real. In this paper, we show that starting from a graph G whose I( G; x) has only real roots, one can build an infinite family of graphs, some being well-covered, whose independence polynomials have only real roots (and, sometimes, are also palindromic). [ABSTRACT FROM AUTHOR]