On Konig-Egervary Square-Stable Graphs

Details On Konig-Egervary Square-Stable Graphs On Konig-Egervary Square-Stable Graphs

2009-08-10

arxiv.org/abs/0908.1313v3

Mathematics

Combinatorics

12 pages, 9 figures

Scientific paper

The stability number of a graph G, denoted by alpha(G), is the cardinality of a maximum stable set, and mu(G) is the cardinality of a maximum matching in G. If alpha(G)+mu(G) equals its order, then G is a Konig-Egervary graph. In this paper we deal with square-stable graphs, i.e., the graphs G enjoying the equality alpha(G)=alpha(G^{2}), where G^{2} denotes the second power of G. In particular, we show that a Konig-Egervary graph is square-stable if and only if it has a perfect matching consisting of pendant edges, and in consequence, we deduce that well-covered trees are exactly the square-stable trees.

Affiliated with

Also associated with

No associations

Rating

On Konig-Egervary Square-Stable Graphs 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 On Konig-Egervary Square-Stable Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Konig-Egervary Square-Stable Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-120503