Combinatorial properties of the family of maximum stable sets of a graph
The stability number?(G) of a graph G is the size of a maximum stable set of G, core is a maximum stable set inG}, 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 KnigEgervry 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 KnigEgervry graphs, and, it is sufficient to check Hall's condition only for one specific stable set, namely for core(G).
maximum stable set bipartite graph hall's marriage theorem maximum matching quasi-regularizable graph ?-stable graph knig-egervry graph