Sách On the number of independent sets in a tree

1 The number of independent sets in a tree
A set of vertices in a graph G is called independent if the set induces no edges. We
write i(G) for the number of independent sets in G; i(G) is often known as the Fibonacci
number, or in mathematical chemistry as the Merrifield-Simmons index or the σ-index.
The study was initiated by Prodinger and Tichy in [4]. In particular, they showed that
among trees of the same order, the maximum and minimum Fibonacci numbers are at-
tained by the star and the path respectively. The name stems from the fact that the
Fibonacci numbers of paths are the usual Fibonacci numbers. Indeed, as the empty set
is independent, i(P0) = 1, i(P1) = 2 and i(Pn) = i(Pnư 1) + i(Pnư 2) for n > 2.
The inverse question asks for a positive integer k, whether there exists a graph G such
that i(G) = k. Clearly there does as i(Kkư 1) = k (note that the empty set is independent).
The question becomes more interesting if we restrict ourselves to certain classes of graphs.
For the class of bipartite graphs, Linek [3] answered the question affirmatively. Here we
are interested in the class of trees. For k ∈ N, we say that k is constructible if there
exists a tree T such that i(T ) = k. For example, 1, 2, 3 are constructible (from the paths
P0, P1, P2 respectively) but 4 is not. In [3], Linek raised the following conjecture (see also