






















The family of all $k$-independent 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 leafs. 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 leafs. We use this tool to show that caterpillars and sunlet graphs satisfy Hurlbert and Kamat's conjecture, and to show that the centers of the largest stars in lobsters are either leafs or spinal vertices of degree 2.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。