1-Konig-Egervary Graphs

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 \textit{K\"{o}nig-Egerv\'{a}ry graph. If $\alpha (G)+\mu(G)=\left\vert V\right\vert -1$, then $G$ is an $1$-K\"{o}nig-Egerv\'{a}ry graph. If $G$ is not a K\"{o}nig-Egerv\'{a}ry graph, and there exists a vertex $v\in V$ (an edge $e\in E$) such that $G-v$ ($G-e$) is K\"{o}nig-Egerv\'{a}ry, then $G$ is called a vertex (an edge) almost K\"{o}nig-Egerv\'{a}ry graph (respectively). In this paper, we characterize all these types of almost K\"{o}nig-Egerv\'{a}ry graphs and present interrelationships between them.