Critical Independent Sets and König-Egerváry Graphs

A set S of vertices is independent or stable in a graph G, and we write S ∈ Ind (G), if no two vertices from S are adjacent, and α(G) is the cardinality of an independent set of maximum size, while core(G) denotes the intersection of all maximum independent sets. G is called a König-Egerváry graph if its order equals α(G) + μ(G), where μ(G) denotes the size of a maximum matching. The number def (G) = {pipe}V(G){pipe} -2μ(G) is the deficiency of G. The number def(G)={pipe}V(G){pipe}-2μ(G) is the deficiency of G. The number d(G)=max{{pipe}S{pipe}-{pipe}N(A){pipe}=d(G)}, where N(S) is the neighbourhood of S, and α _c(G) denotes the maximum size of a critical independent set. Lrson (Eur J Comb 32:294-300, 2011)demonstrated that G is a k̈nig-Egerváry graph if and only if there exists a maximum independent set that is also critical, i.e., α _c(G)=α(G). In this paper we prove that: (i) d(G)={pipe}(G){pipe}-{pipe}N(core(G)){pipe}=α(G)=def(G) holds for every König-Egerváry graph G; (ii) G is König-Egerváry graph if and only if each maximum independent set of G is critical.