Very well-covered graphs with the Erdős–Ko–Rado property

De Silva, Jessica; Dionne, Adam B.; Dunkelberg, Aidan; Harris, Pamela E.

doi:10.2140/involve.2023.16.35

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

Very well-covered graphs with the Erdős–Ko–Rado property

Jessica De Silva, Adam B. Dionne, Aidan Dunkelberg and Pamela E. Harris

Vol. 16 (2023), No. 1, 35–47

DOI: 10.2140/involve.2023.16.35

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 conjectured that a graph is $r$ -EKR as long as $1 \leq r \leq \frac{1}{2} μ (G)$ , where $μ (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 2 r$ and strictly so when $n > 2 r$ . Pendant path graphs $P_{n}^{*}$ are also explored and the vertex whose $r$ -star is of maximum size is determined.

Keywords

graph theory, independent sets, extremal, Erdős–Ko–Rado, combinatorics, well-covered

Mathematical Subject Classification

Primary: 05C35, 05C69

Milestones

Received: 9 July 2021

Revised: 6 March 2022

Accepted: 5 April 2022

Published: 14 April 2023

Communicated by Glenn Hurlbert

Authors

Jessica De Silva
Department of Mathematics California State University, Stanislaus Turlock, CA United States

Adam B. Dionne
Department of Mathematics and Statistics Williams College Williamstown, MA United States

Aidan Dunkelberg
Department of Mathematics and Statistics Williams College Williamstown, MA United States

Pamela E. Harris
Department of Mathematical Sciences University of Wisconsin Milwaukee Milwaukee, WI United States

Vol. 16, No. 1, 2023