On the Critical Difference of Almost Bipartite Graphs

Abstract

A set $S\subseteq V$ is \textit{independent} in a graph $G=\left(V,E\right)$ if no two vertices from $S$ are adjacent. The \textit{independence number} $\alpha (G)$ is the cardinality of a maximum independent set, while $\mu (G)$ is the size of a maximum matching in $G$. If $\alpha (G)+\mu (G)$ equals the order of $G$, then $G$ is called a \textit{König-Egerváry graph }\cite{dem,ster}. The number $d\left(G\right)=\max \{\left|A\right|-\left|N\left(A\right)\right|:A\subseteq V\}$ is called the \textit{critical difference} of $G$ \cite{Zhang} (where $N\left(A\right)=\left\{v:v\in V,N\left(v\right)\cap A\ne \varnothing \right\}$). It is known that $\alpha (G)-\mu (G)\le d\left(G\right)$ holds for every graph \cite{Levman2011a,Lorentzen1966,Schrijver2003}. In \cite{LevMan5} it was shown that $d(G)=\alpha (G)-\mu (G)$ is true for every König-Egerváry graph. A graph $G$ is \textit{(i)} \textit{unicyclic} if it has a unique cycle, \textit{(ii)} \textit{almost bipartite} if it has only one odd cycle. It was conjectured in \cite{LevMan2012a,LevMan2013a} and validated in \cite{Bhattacharya2018} that $d(G)=\alpha (G)-\mu (G)$ holds for every unicyclic non-König-Egerváry graph $G$. In this paper we prove that if $G$ is an almost bipartite graph of order $n\left(G\right)$, then $\alpha (G)+\mu (G)\in \left\{n\left(G\right)-1,n\left(G\right)\right\}$. Moreover, for each of these two values, we characterize the corresponding graphs. Further, using these findings, we show that the critical difference of an almost bipartite graph $G$ satisfies \[ d(G)=α(G)-μ(G)=\left\vert \mathrm{core}(G)\right\vert -\left\vert N(\mathrm{core}(G))\right\vert , \] where by \textrm{core}$\left(G\right)$ we mean the intersection of all maximum independent sets.

12 pages, 5 figures. arXiv admin note: text overlap with arXiv:1102.4727