Critical Sets in Bipartite Graphs

Abstract

Let G =  (V, E) be a graph. A set ${I \subseteq V}$ is independent if no two vertices from I are adjacent, and by Ind(G) we mean the family of all independent sets of G, while core(G) is the intersection of all maximum independent sets [4]. The number ${d_{c}(G) = {\rm max}\{|I| - |N(I)| : I \in {\rm Ind}(G)\}}$ is called the critical difference of G. A set X is critical if ${|X| - |N(X)| = d_{c}(G)}$ [10]. For a bipartite graph G =  (A, B, E), Ore [7] defined ${\delta_{0} (A) = {\rm max}\{|X| - |N(X)| : X \subseteq A\}}$ . In this paper, we prove that ${d_{c} (G) = \delta_{0} (A)+\delta_{0} (B)}$ and ker(G) = core(G) hold for every bipartite graph G =  (A, B, E), where ker(G) denotes the intersection of all critical independent sets.