Graphs, partitions and Fibonacci numbers |
| |
Authors: | Arnold Knopfmacher |
| |
Institution: | a The John Knopfmacher Centre for Applicable Analysis and Number Theory, University of the Witwatersrand, Johannesburg, Private Bag 3, WITS 2050, South Africa b Department of Mathematics, Graz University of Technology, Steyrergasse 30, A-8010 Graz, Austria |
| |
Abstract: | 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 have diameter ?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) is asymptotically for constants A,B as n→∞. This is proved by using a natural correspondence between partitions of integers and star-like trees. |
| |
Keywords: | Star-like tree Partition Fibonacci number Independent set |
本文献已被 ScienceDirect 等数据库收录! |
|