On the critical difference of almost bipartite graphs

Journal of Algebraic Combinatorics - A set $$S\subseteq V$$ is independent in a graph $$G=\left( V,E\right) $$ if no two vertices from S are adjacent. The independence number $$\alpha (G)$$ is the...     

Critical Independent Sets and König–Egerváry Graphs

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 α _c (G) denotes the maximum size of a critical independent set. Larson (Eur J Comb 32:294–300, 2011) 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., α _c (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.     

When is G 2 a König–Egerváry Graph?

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.     

A simple proof of an inequality connecting the alternating number of independent sets and the decycling number

If s_k denotes the number of independent sets of cardinality k and α(G) is the size of a maximum independent set in graph G, then I(G;x)=s₀+s₁x+?+s_α(G)x^α(G) is the independence polynomial of G (Gutman and Harary, 1983) [8].In this paper we provide an elementary proof of the inequality|I(G;−1)|≤2^φ(G) (Engström, 2009) [7], where φ(G) is the decycling number of G (Beineke and Vandell, 1997) [3], namely, the minimum number of vertices that have to be deleted in order to turn G into a forest.     

On Unicyclic Graphs with Uniquely Restricted Maximum Matchings

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, μ _r (G) ≤ μ(G), where μ _r (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 μ _r (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.     

On maximum matchings in König–Egerváry graphs

For a graph $G$ let $\alpha \left(G\right),\mu \left(G\right)$, and $\tau \left(G\right)$ denote its independence number, matching number, and vertex cover number, respectively. If $\alpha \left(G\right)+\mu \left(G\right)=\left|V\left(G\right)\right|$ or, equivalently, $\mu \left(G\right)=\tau \left(G\right)$, then $G$ is a König–Egerváry graph.In this paper we give a new characterization of König–Egerváry graphs.     

Building Graphs Whose Independence Polynomials Have Only Real Roots

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

$I(G; x) = s_{0}+s_{1}x+s_{2}x^{2}+\cdots+s_{\alpha}x^{\alpha},\alpha=\alpha(G),$

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

The Cyclomatic Number of a Graph and its Independence Polynomial at −1

If by s _k 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, 1983), where α = α(G) is the size of a maximum independent set. The inequality |I (G; ?1)| ≤ 2 ^ν(G), where ν(G) is the cyclomatic number of G, is due to (Engström in Eur. J. Comb. 30:429–438, 2009) and (Levit and Mandrescu in Discret. Math. 311:1204–1206, 2011). 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 ^ν(G), 2 ^ν(G)} are sharp for I (G; ?1), and investigate other values of I (G; ?1) belonging to the interval [?2 ^ν(G), 2 ^ν(G)].