Combinatorial properties of the family of maximum stable sets of a graph Original Research Article

The stability number α(G) of a graph G is the size of a maximum stable set of G, core(G)=⋂{S : S is a maximum stable set in G}, and ξ(G)=|core(G)|. In this paper we prove that for a graph G the following assertions are true: (i) if G has no isolated vertices, and ξ(G)⩽1, then G is quasi-regularizable; (ii) if the order of G is n, and α(G)>(n+k−min{1,|N(core(G))|})/2, for some k⩾1, then ξ(G)⩾k+1; moreover, if n+k−min{1,|N(core(G))|} is even, then ξ(G)⩾k+2. The last finding is a strengthening of a result of Hammer, Hansen, and Simeone, which states that ξ(G)⩾1 is true whenever α(G)>n/2. In the case of König–Egerváry graphs, i.e., for graphs enjoying the equality α(G)+μ(G)=n, where μ(G) is the maximum size of a matching of G, we prove that |core(G)|>|N(core(G))| is a necessary and sufficient condition for α(G)>n/2. Furthermore, for bipartite graphs without isolated vertices, ξ(G)⩾2 is equivalent to α(G)>n/2. We also show that Hallʹs Marriage Theorem is true for König–Egerváry graphs, and, it is sufficient to check Hallʹs condition only for one specific stable set, namely for core(G).