•  
  •  
 

Turkish Journal of Mathematics

ZAKİR DENİZ

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

Download

Included in

Mathematics Commons

Share

COinS