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

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

1999-12-06

arxiv.org/abs/math/9912047v1

Mathematics

Combinatorics

13 pages; 10 figures

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Combinatorial Properties of the Family of Maximum Stable Sets of a Graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Combinatorial Properties of the Family of Maximum Stable Sets of a Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial Properties of the Family of Maximum Stable Sets of a Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-573813