On α+-stable König-Egerváry graphs

The stability number of a graph G, denoted by α(G), is the cardinality of a stable set of maximum size in G. If its stability number remains the same upon the addition of any edge, then G is called α ⁺-stable. G is a König-Egerváry graph if its order equals α(G)+μ(G), where μ(G) is the size of a maximum matching in G. In this paper, we characterize α ⁺-stable König-Egerváry graphs, generalizing some previously known results on bipartite graphs and trees. Namely, we prove that a König-Egerváry graph G=(V,E) of order at least two is α ⁺-stable if and only if G has a perfect matching and |∩{V-S: S∈Ω(G)}|1 (where Ω(G) denotes the family of all maximum stable sets of G). We also show that the equality |∩{V-S: S∈Ω(G)}|=|∩{S: S∈Ω(G)}| is a necessary and sufficient condition for a König-Egerváry graph G to have a perfect matching. Finally, we describe the two following types of α ⁺-stable König-Egerváry graphs: those with |∩{S: S∈Ω(G)}|=0 and |∩{S: S∈Ω(G)}|=1, respectively.