The Intersection of All Maximum Stable Sets of a Tree and its Pendant Vertices

Details The Intersection of All Maximum Stable Sets of a Tree and its Pendant Vertices The Intersection of All Maximum Stable Sets of a Tree and its Pendant Vertices

1999-12-06

arxiv.org/abs/math/9912048v2

Mathematics

Combinatorics

10 pages; 6 figures

Scientific paper

One theorem of Nemhauser and Trotter ensures that, under certain conditions, a stable set of a graph G can be enlarged to a maximum stable set of this graph. For example, any stable set consisting of only simplicial vertices is contained in a maximum stable set of G. In this paper we demonstrate that an inverse assertion is true for trees of order greater than one, where, in fact, all the simplicial vertices are pendant. Namely, we show that any maximum stable set of such a tree contains at least one pendant vertex. Moreover, we prove that if T does not own a perfect matching, then a stable set, consisting of at least two pendant vertices, is included in the intersection of all its maximum stable sets. For trees, the above assertion is also a strengthening of one result of Hammer, Hansen, and Simeone, stating that if half of order of G is less than the cardinality of a maximum stable set of G, then the intersection of all its maximum stable sets is non-empty.

Affiliated with

Also associated with

No associations

Rating

The Intersection of All Maximum Stable Sets of a Tree and its Pendant Vertices 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 The Intersection of All Maximum Stable Sets of a Tree and its Pendant Vertices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Intersection of All Maximum Stable Sets of a Tree and its Pendant Vertices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-573818