A classification of 1-well-covered graphs

A graph is well-covered if all its maximal independent sets have the same size. If a graph is well-covered and remains well-covered upon removal of any vertex, then it is called 1-well-covered graph. It is well-known that [n/2]+1≤ α(G) + μ(G) ≤ n for any graph G with n vertices where α(G) and μ(G) are the independence and matching numbers of G, respectively. A graph G satisfying α(G) + μ(G) = n is known as König-Egervary graph, and such graphs are characterized by Levit and Mandrescu [14] under the assumption that G is 1-well-covered. In this paper, we investigate connected 1-well-covered graphs with respect to α(G) + μ(G)=n-k for k≥ 1 and $ G =n$. We further present some combinatorial properties of such graphs. In particular, we provide a tight upper bound on the size of those graphs in terms of k, namely G ≤ 10k-2, also we show that Δ(G)≤ 2k+1 and α(G)≤ min \4k-1,n-2k\. This particularly enables us to obtain a characterization of such graphs for $k=1$, which settles a problem of Levit and Mandrescu [14].