Let $\alpha(G)$ denote the cardinality of a maximum independent set, while $\mu(G)$ be the size of a maximum matching in $G=\left( V,E\right) $. It is known that if $\alpha(G)+\mu(G)=\left\vert V\right\vert $, then $G$ is a K\"{ o}nig-Egerv\'{ a}ry graph. The critical difference $d(G)$ is $\max\{ d(I):I\in\mathrm{ Ind}(G)\}$, where $\mathrm{ Ind}(G)$\ denotes the family of all independent sets of $G$. If $A\in\mathrm{ Ind}(G)$ with $d\left( X\right) =d(G)$, then $A$ is a critical independent set. For a graph $G$, let $\mathrm{ diadem}(G)=\bigcup\{ S:S$ is a critical independent set in $G\}$, and $\varrho_{ v}\left( G\right) $ denote the number of vertices $v\in V\left( G\right) $, 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 $\left\lfloor { V(C)}/{ 2}\right\rfloor $ edges belonging to $C$; 2. $V(C)\cup N_{ G}\left[ \mathrm{ diadem}\left( G\right) \right] =V$ and $V(C)\cap N_{ G}\left[ \mathrm{ diadem}\left( G\right) \right] =\emptyset$; 3. $\varrho_{ v}\left( G\right) =\left\vert \mathrm{ corona}\left( G\right) \right\vert -\left\vert \mathrm{ diadem}\left( G\right) \right\vert $, where $\mathrm{ corona}\left( G\right) $ is the union of all maximum independent sets of $G$; 4. $\varrho_{ v}\left( G\right) =\left\vert V\right\vert $ if and only if $G=C_{ 2k+1}$ for some integer $k\geq1$.

Categories: math.CO cs.DM

Almost Bipartite non-K\