On almost bipartite non-König–Egerváry graphs

A set S ⊆ V is independent in a graph G = V , E if no two vertices from S are adjacent. The independence number α ( G ) is the cardinality of a maximum independent set, while μ ( G ) is the size of a maximum matching in G . If α ( G ) + μ ( G ) equals the order of G , then G is a König–Egerváry graph (Deming, 1979; Gavril, 1977; Sterboul, 1979). The number d G = max { A − N A : A ⊆ V } is the critical difference of G (Zhang, 1990) (where N A = v : v ∈ V , N v ∩ A ≠ 0̸ ). It is known that the inequality α ( G ) − μ ( G ) ≤ d G holds for every graph (Levit and Mandrescu, 2012; Lorentzen, 1966; Schrijver, 2003). A graph G is (i) unicyclic if it has a unique cycle, (ii) almost bipartite if it has only one odd cycle. Let ker ( G ) = ⋂ { S : S is a critical independent set of G } , core G be the intersection of all maximum independent sets, and corona G be the union of all maximum independent sets of G . It is known that ker ( G ) ⊆ core ( G ) for every graph (Levit and Mandrescu, 2012), while the equality holds for bipartite graphs (Levit and Mandrescu, 2013), and for unicyclic non-König–Egerváry graphs (Levit and Mandrescu, 2014). In this paper, we prove that if G is an almost bipartite non-König–Egerváry graph, then ker ( G ) = core ( G ) , corona ( G ) ∪ N (core( G )) = V ( G ) , and corona ( G ) + core ( G ) = 2 α ( G ) + 1 .