2009/06/25 by Vadim E. Levit, Levit, Vadim E., Eugen Mândrescu +2
Computer Science · Mathematics · #05C69 #05C70 (Primary) #05C75 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #cs.DM #math.CO #msc:05C69 #msc:05C70 #msc:05C75
paper · pdf · doi:10.48550/arxiv.0906.4609
8 pages, 5 figures
openalex publication_date 2009/06/25 · arxiv created 2009/06/30 · arxiv updated 2011/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.