Graphs, Partitions and Fibonacci Numbers..pdfVIP

Graphs, Partitions and Fibonacci Numbers. Dedicated to Professor Helmut Prodinger on the occasion of his 50th birthday Arnold Knopfmacher a Robert F. Tichy b Stephan Wagner b Volker Ziegler b 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 A ·2n ·exp(B √n) ·n3/4 for constants A, B as n → ∞. This is proved by using a natural correspondence between partitions of integers and star-like trees. Key words: Star-like tree, partition, Fibonacci number, independent set 1 Introduction Let G = (V (G), E(G)) denote a graph with vertex set V (G) and edge set E (G). All graphs considered here are finite and simple. In general we will use The work was supported by Austrian Science Fund project no. S-8307-MAT. Email addresses: arnoldk@cam.wits.ac.za (Arnold Knopfmacher), tichy@tugraz.at (Robert F. Tichy), wagner@finanz.math.tugraz.at (Stephan Wagner), ziegler@finanz.math.tugraz.at (Volker Ziegler). Preprint submitted to Discrete Applied Mathematics 27 October 2006 the terminology introduced in [5]. We will write G \ {v , v , . . .} fo