Almost Bipartite non-K\"onig-Egerv\'ary Graphs Revisited

Let α(G) denote the cardinality of a maximum independent set, while μ(G) be the size of a maximum matching in G=( V,E). It is known that if α(G)+μ(G)= V, then G is a K\"{o}nig-Egerv\'{a}ry graph. The critical difference $d(G)$ is max(I):I(G)\, where Ind(G)\ denotes the family of all independent sets of G. If A(G) with d( X) =d(G), then A is a critical independent set. For a graph G, let diadem(G)=:S is a critical independent set in G\, and ᵥ( G) denote the number of vertices v∈ V( G), such that $G-v$ is a K\"{o}nig-Egerv\'{a}ry graph. A graph is called almost bipartite if it has a unique odd cycle. In this paper, we show that if G is an almost bipartite non-K\"{o}nig-Egerv\'{a}ry graph with the unique odd cycle C, then the following assertions are true: 1. every maximum matching of G contains V(C)/2 edges belonging to C; 2. V(C)∪ NG[ diadem( G) ] =V and V(C)∩ NG[ diadem( G) ] =∅; 3. ᵥ( G) = corona( G) - diadem( G), where corona( G) is the union of all maximum independent sets of G; 4. ᵥ( G) = V if and only if G=C₂ₖ₊₁ for some integer k≥1.