On stars in caterpillars and lobsters

Abstract

The family of all independent k-sets of a graph containing a fixed vertex v is called a star and v is called its center. Stars are interesting for their relation to Erdős–Ko–Rado graphs. Hurlbert and Kamat conjectured that in trees the largest stars are centered in leaves. This conjecture was disproven independently by Baber, Borg, and Feghali, Johnson, and Thomas. In this paper we introduce a tool to bound the size of stars centered at certain vertices by stars centered at leaves. We use this tool to show that caterpillars satisfy Hurlbert and Kamat's conjecture, and that the centers of the largest stars in lobsters are either leaves or spinal vertices of degree 2.