Stars on trees

Abstract

For a positive integer $r$ and a vertex $v$ of a graph $G$, let ${\mathcal{I}}_G^{(r)}(v)$ denote the set of all independent sets of $G$ that have exactly $r$ elements and contain $v$. Hurlbert and Kamat conjectured that for any $r$ and any tree $T$, there exists a leaf $z$ of $T$ such that $|{\mathcal{I}}_T^{(r)}(v)|\le |{\mathcal{I}}_T^{(r)}(z)|$ for each vertex $v$ of $T$. They proved the conjecture for $r\le 4$. For any $k\ge 3$, we construct a tree $T_k$ that has a vertex $x$ such that $x$ is not a leaf of $T_k$, $|{\mathcal{I}}_{T_k}^{(r)}(z)|<|{\mathcal{I}}_{T_k}^{(r)}(x)|$ for any leaf $z$ of $T_k$ and any $5\le r\le 2k+1$, and $2k+1$ is the largest integer $s$ for which ${\mathcal{I}}_{T_k}^{(s)}(x)$ is non-empty. Therefore, the conjecture is not true for $r\ge 5$.

5 pages