Graphs, partitions and Fibonacci numbers (Q2370416)

The Fibonacci number of a graph \(G\) is the number \(F(G)\) of independent vertex subets it has. The authors say a tree is star-like if its diameter is at most 4. They show that there are \(p(n)- \lfloor n/2\rfloor\) such trees with \(n\) edges, where \(p(n)\) is the number of partitions of \(n\), and that the average Fibonacci number of such trees is asymptotic to \(A\cdot 2^n\exp(B\sqrt{n})\cdot n^{3/4}\), where \(A= 2.739\dots\) and \(B= -1.039\dots\). They also show, among other things, that all trees \(T\) with \(n\) edges such that \(2^{n-1}+ 5< F(T)\leq 2^n+ 1\) are star-like and they order these trees with respect to their Fibonacci numbers.