On 1-König-Egerváry Graphs

Abstract Let $$\alpha (G)$$ α ( G ) denote the cardinality of a maximum independent set, while $$\mu (G)$$ μ ( G ) be the size of a maximum matching in $$G=\left( V,E\right) $$ G = V , E . Let $$\xi (G)$$ ξ ( G ) denote the size of the intersection of all maximum independent sets [12]. It is known that if $$\alpha (G)+\mu (G)=n(G)=\left| V\right| $$ α ( G ) + μ ( G ) = n ( G ) = V , then G is a König-Egerváry graph [5, 7, 24]. If $$\alpha (G)+\mu (G)=n(G)-1$$ α ( G ) + μ ( 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$$ v ∈ V (an edge $$e\in E$$ e ∈ E ) such that $$G-v$$ G - v ( $$G-e$$ G - e ) is König-Egerváry, then G is called a vertex (an edge) almost König-Egerváry graph (respectively). For $$X\subseteq V(G)$$ X ⊆ V ( G ) , the number $$\left| X\right| -\left| N(X)\right| $$ X