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

Submission Guidelines

Submission Form

Policies for Authors

Ethics Statement

ISSN: 1944-4184 (e-only)

ISSN: 1944-4176 (print)

Author Index

Coming Soon

Other MSP Journals

This article is available for purchase or by subscription. See below.

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.

PDF Access Denied

We have not been able to recognize your IP address 18.117.107.90 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 30.00:

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