A characterization of graphs with $\a{\corona G}+\a{\core G}=2α(G)+1$

Abstract

A Kőnig--Egerváry graph is a graph $G$ satisfying $\alpha (G)+\mu (G)=n(G)$, where $\alpha (G)$, $\mu (G)$, and $n(G)$ denote the independence number, the matching number, and the order of $G$, respectively. Let $\text{core}(G)$ and $\text{corona}(G)$ be the intersection and the union of all maximum independent sets of $G$. In this paper, we provide a complete characterization of graphs satisfying $\a{\corona G}+\a{\core G}=2α(G)+1$, thus giving a solution to an open problem posed by Levit and Mandrescu. It is known that for a non-Kőnig--Egerváry graph with a unique odd cycle, the following hold: $\ker G=\text{core}(G),\left|\text{corona}(G)\right|+\left|\text{core}(G)\right|=2\alpha (G)+1,\text{corona}(G)\cup N(\text{core}(G))=V(G)$. We extend these three results to a family of graphs containing an arbitrarily large number of odd cycles.