Graphs, partitions and Fibonacci numbers

被引：25

作者：

Knopfmacher, Arnold

Tichy, Robert F.

Wagner, Stephan

Ziegler, Volker

机构：

[1] Univ Witwatersrand, John Knopfmacher Ctr Applicable Anal & Number The, ZA-2050 Johannesburg, South Africa

[2] Graz Univ Technol, Dept Math, A-8010 Graz, Austria

来源：

DISCRETE APPLIED MATHEMATICS | 2007年 / 155卷 / 10期

基金：

奥地利科学基金会;

关键词：

star-like tree; partition; Fibonacci number; independent set;

D O I：

10.1016/j.dam.2006.10.010

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 > 2(n-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.2(n).exp(B root n).n(3/4) for constants A, B as n ->infinity. This is proved by using a natural correspondence between partitions of integers and star-like trees. (c) 2006 Elsevier B.V. All rights reserved.

引用

页码：1175 / 1187

页数：13