Critical independent sets and Konig--Egervary graphs

Details Critical independent sets and Konig--Egervary graphs Critical independent sets and Konig--Egervary graphs

2009-06-25

arxiv.org/abs/0906.4609v2

Mathematics

Combinatorics

8 pages, 5 figures

Scientific paper

Let alpha(G) be the cardinality of a independence set of maximum size in the graph G, while mu(G) is the size of a maximum matching. G is a Konig--Egervary graph if its order equals alpha(G) + mu(G). The set core(G) is the intersection of all maximum independent sets of G (Levit & Mandrescu, 2002). The number def(G)=|V(G)|-2*mu(G) is the deficiency of G (Lovasz & Plummer, 1986). The number d(G)=max{|S|-|N(S)|:S in Ind(G)} is the critical difference of G. An independent set A is critical if |A|-|N(A)|=d(G), where N(S) is the neighborhood of S (Zhang, 1990). In 2009, Larson showed that G is Konig--Egervary graph if and only if there exists a maximum independent set that is critical as well. In this paper we prove that: (i) d(G)=|core(G)|-|N(core(G))|=alpha(G)-mu(G)=def(G) for every Konig--Egervary graph G; (ii) G is Konig--Egervary graph if and only if every maximum independent set of G is critical.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-536751