Combinatorial Properties of the Family of Maximum Stable Sets of a Graph

Simple item page
dc.creatorLevit, Vadim E.
dc.creatorMandrescu, Eugen
dc.date1999-12-06
dc.date.accessioned2026-07-07T05:32:09Z
dc.date.available2026-07-07T05:32:09Z
dc.descriptionThe stability number alpha(G) of a graph G is the cardinality of a maximum stable set in G, xi(G) denotes the size of core(G), where core(G) is the intersection of all maximum stable sets of G. In this paper we prove that for a graph G without isolated vertices, the following assertions are true: (i) if xi(G)< 2, then G is quasi-regularizable; (ii) if G is of order n and alpha(G) > (n+k-1)/2, for some k > 0, then xi(G) > k, and xi(G) > k+1, whenever n+k-1 is even. The last finding is a strengthening of a result of Hammer, Hansen, and Simeone, which states that alpha(G) > n/2 implies xi(G) > 0. G is a Koenig-Egervary graph if n equals the sum of its stability number and the cardinality of a maximum matching. For Koenig-Egervary graphs, we prove that alpha(G) > n/2 holds if and only if xi(G) is greater than the size of the neighborhood of core(G). Moreover, for bipartite graphs without isolated vertices, alpha(G) > n/2 is equivalent to xi(G) > 1. We also show that Hall's marriage Theorem is valid for Koenig-Egervary graphs, and it is sufficient to check Hall's condition only for one specific stable set, namely, for core(G).
dc.description13 pages; 10 figures
dc.identifierhttps://arxiv.org/abs/math/9912047
dc.identifierhttp://arxiv.org/abs/math/9912047
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/79555
dc.subjectCombinatorics
dc.subject05C69 (Primary) 05C70 (Secondary)
dc.titleCombinatorial Properties of the Family of Maximum Stable Sets of a Graph
dc.typetext

Files

Collections

arXiv