Stars on trees

For a positive integer r and a vertex v of a graph G, let I-G((r))(v) denote the set of independent sets of G that have exactly r elements and contain v. Motivated by a problem of Holroyd and Talbot, Hurlbert and Kamat conjectured that for any r and any tree T, there exists a leaf z of T such that |I-T((r))(v)| <= |I-T((r))(z)| for each vertex v of T. They proved the conjecture for r <= 4. We show that for any integer k >= 3, there exists a tree T-k that has a vertex x such that x is not a leaf of T-k, |I-Tk((r))(z)| < |I-Tk((r))(x)| for any leaf z of T-k and any integer r with 5 <= r <= 2k + 1, and 2k 1 is the largest integers for which I-Tk((s))(x) is non-empty. (C) 2016 Elsevier B.V. All rights reserved.