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

Institutions

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

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

1-well-covered graphs containing a clique of size n∕3

Zakir Deniz
Electronic Journal of Graph Theory and Applications
Advanced Graph Theory Research
article

1-well-covered graphs containing a clique of size n∕3

Zakir Deniz
article en

Abstract

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.

Electronic Journal of Graph Theory and ApplicationsVol. 12(2)
Düzce Üniversitesi (TR)
Türkiye Bilimsel ve Teknolojik Araştırma Kurumu
Openalex Percentile: Top 73%
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.