Download this article
Download this article For screen
For printing
Recent Issues

Volume 17, 1 issue

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the Journal
Editorial Board
Editors’ Interests
Subscriptions
 
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
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
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 r 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 Kn is r-EKR when n 2r and strictly so when n > 2r. Pendant path graphs Pn 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