A classification of 1-well-covered graphs

Abstract

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-Egerváry 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].