Published January 1, 2024 | Version v1
Journal article Open

1-well-covered graphs containing a clique of size <i>n</i>/3

Creators

  • 1. Duzce Univ, Dept Math, TR-81620 Duzce, Turkiye

Description

A graph is well-covered if all of its maximal independent sets have the same size. A graph that remains well-covered upon the removal of any vertex is called a 1-well-covered graph. These graphs, when they have no isolated vertices, are also known as W-2 graphs. It is well-known that every graph G is an element of W-2 has two disjoint maximum independent sets. In this paper, we investigate connected W-2 graphs with n vertices that contain a clique of size n/3. We prove that if the removal of two disjoint maximum independent sets from a graph G is an element of W-2 leaves a clique of size at least 3, then G contains a clique of size n/3. Using this result, we provide a complete characterization of these graphs, based on eleven graph families.

Files

bib-5dcd743c-e24d-47c4-b535-1a1dca89138e.txt

Files (151 Bytes)

Name Size Download all
md5:bcb68ecb49852eb1576de56fc6704912
151 Bytes Preview Download