# Turkish Journal of Mathematics

## DOI

10.3906/mat-2105-45

## 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

## First Page

2817

## Last Page

2829

## Recommended Citation

DENİZ, ZAKİR
(2021)
"A classification of 1-well-covered graphs,"
*Turkish Journal of Mathematics*: Vol. 45:
No.
6, Article 27.
https://doi.org/10.3906/mat-2105-45

Available at:
https://journals.tubitak.gov.tr/math/vol45/iss6/27