Authors: ZAKİR DENİZ

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 $[\frac{n}{2}]+1\leq \alpha(G) + \mu(G) \leq n$ for any graph $G$ with $n$ vertices where $\alpha(G)$ and $\mu(G)$ are the independence and matching numbers of $G$, respectively. A graph $G$ satisfying $\alpha(G) + \mu(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 $\alpha(G) + \mu(G)=n-k$ for $k\geq 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|\leq 10k-2$, also we show that $\Delta(G)\leq 2k+1$ and $\alpha(G)\leq \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].

Keywords: Independent set, matching, well-covered

Full Text: PDF