1-well-covered graphs containing a clique of size n∕3
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 ∈ 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 ∈ 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.
Authors
- Zakir Deniz (ORCID: https://orcid.org/0000-0002-0701-0397)
Institutions
- Düzce Üniversitesi (TR)
Publication Details
- Journal
- Electronic Journal of Graph Theory and Applications
- Published
- 2024-10-24
- DOI
- https://doi.org/10.5614/ejgta.2024.12.2.8
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Türkiye Bilimsel ve Teknolojik Araştırma Kurumu