论文标题
在毛毛虫和龙虾的星星上
On Stars in Caterpillars and Lobsters
论文作者
论文摘要
包含固定顶点$ v $的图的所有无关的$ k $的家族称为{star}，$ v $称为其中心。星星与Erdös-Ko-Rado图有关，很有趣。赫尔伯特（Hurlbert）和卡玛特（Kamat）猜想，在树木中，最大的恒星以叶子为中心。这个猜想是由Baber，Borg和Feghali，Johnson和Thomas独立驳斥的。在本文中，我们引入了一种工具，以绑定以叶子为中心的恒星以某些顶点为中心的恒星的大小。我们使用此工具来表明毛毛虫和阳光图满足了赫尔伯特和卡玛特的猜想，并表明龙虾中最大的恒星的中心是叶子或脊柱2。
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.
