On the Number of Vertices/Edges whose Deletion Preserves the Konig-Egervary Property

The graph G=(V,E) is called Konig-Egervary if the sum of its independencenumber and its matching number equals its order. Let RV(G) denote the number ofvertices v such that G-v is Konig-Egervary, and let RE(G) denote the number ofedges e such that G-e is Konig-Egervary. Clearly, RV(G) = |V| and RE(G) = |E|for bipartite graphs. Unlike the bipartiteness, the property of being aKonig-Egervary graph is not hereditary. In this paper, we present an equalityexpressing RV(G) in terms of some graph parameters, and a tight inequalitybounding RE(G) in terms of the same parameters, when G is Konig-Egervary.