Eugen Mândrescu
Holon Institute of Technology, Holon, Israel

Let $\alpha(G)$ denote the cardinality of a maximum independent set, while $\mu(G)$ be the size of a maximum matching in graph $G=(V,E)$ . If $\alpha(G)+\mu(G)=|V|$, then G is called a König-Egerváry graph, while if $\alpha(G)+\mu(G)=\left\vert V\right\vert -1$, then $G$ is an almost König-Egerváry graph.

If $G$ is not a König-Egerváry graph, but 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 almost König-Egerváry (C. E. Larson, R. Pepper, The Electronic Journal of Combinatorics 18 (2011) P180) (an edge almost König-Egerváry graph, respectively).

In this talk, we present some relationships between all these types of almost König-Egerváry graphs, as well as several specific properties.

Joint work with Vadim E. Levit, Ariel University, Israel.