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)| \leq |\mathcal{I}_T^{(r)}(z)|$ for each vertex $v$ of $T$. They proved the conjecture for $r \leq 4$. For any $k \geq 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 \leq r \leq 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 \geq 5$.

5 pages