Graphs, partitions and Fibonacci numbers Original Research Article

The Fibonacci number of a graph is the number of independent vertex subsets. In this paper, we investigate trees with large Fibonacci number. In particular, we show that all trees with n edges and Fibonacci number >2n-1+5>2n-1+5 have diameter ⩽4⩽4 and determine the order of these trees with respect to their Fibonacci numbers. Furthermore, it is shown that the average Fibonacci number of a star-like tree (i.e. diameter ⩽4⩽4) is asymptotically View the MathML sourceA·2n·exp(Bn)·n3/4 for constants A,BA,B as n→∞n→∞. This is proved by using a natural correspondence between partitions of integers and star-like trees.