Back to Search Start Over

Very Well-Covered Graphs with the Erd\H{o}s-Ko-Rado Property

Authors :
De Silva, Jessica
Dionne, Adam B.
Dunkelberg, Aidan
Harris, Pamela E.
Source :
Involve 16 (2023) 35-47
Publication Year :
2021

Abstract

A family of independent $r$-sets of a graph $G$ is an $r$-star if every set in the family contains some fixed vertex $v$. A graph is $r$-EKR if the maximum size of an intersecting family of independent $r$-sets is the size of an $r$-star. Holroyd and Talbot conjecture that a graph is $r$-EKR as long as $1\leq r\leq\frac{\mu(G)}{2}$, where $\mu(G)$ is the minimum size of a maximal independent set. It is suspected that the smallest counterexample to this conjecture is a well-covered graph. Here we consider the class of very well-covered graphs $G^*$ obtained by appending a single pendant edge to each vertex of $G$. We prove that the pendant complete graph $K_n^*$ is $r$-EKR when $n \geq 2r$ and strictly so when $n>2r$. Pendant path graphs $P_n^*$ are also explored and the vertex whose $r$-star is of maximum size is determined.<br />Comment: 10 pages

Subjects

Subjects :
Mathematics - Combinatorics
05C35

Details

Database :
arXiv
Journal :
Involve 16 (2023) 35-47
Publication Type :
Report
Accession number :
edsarx.2106.09067
Document Type :
Working Paper
Full Text :
https://doi.org/10.2140/involve.2023.16.35