On 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=(V,E)$. Let $\xi (G)$ denote the size of the intersection of all maximum independent sets. It is known that if $\alpha (G)+\mu (G)=n(G)=\mid V\mid$, then $G$ is a König-Egerváry graph. If $\alpha (G)+\mu (G)=n(G)-1$, then $G$ is a $1$-König-Egerváry graph. If $G$ is not a König-Egerváry graph, and there exists a vertex $v\in V$ (an edge $e\in E$) such that $G-v$ ($G-e$) is König-Egerváry, then $G$ is called a vertex (an edge) almost König-Egerváry graph (respectively). The critical difference $d(G)$ is $\max \{d(I):I\in \mathrm{I}\mathrm{n}\mathrm{d}(G)\}$, where $\mathrm{I}\mathrm{n}\mathrm{d}(G)$ denotes the family of all independent sets of $G$. If $A\in \mathrm{I}\mathrm{n}\mathrm{d}(G)$ with $d\left(X\right)=d(G)$, then $A$ is a critical independent set. Let $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önig-Egerváry graph. In this paper, we characterize all types of almost König-Egerváry graphs and present interrelationships between them. We also show that if $G$ is a $1$-König-Egerváry graph, then ${\varrho }_v\left(G\right)\le n\left(G\right)+d\left(G\right)-\xi \left(G\right)-\beta (G)$, where $\beta (G)=\mid diadem(G)\mid$. As an application, we characterize the $1$-König-Egerváry graphs that become König-Egerváry after deleting any vertex.