Stephan Wagner: Enumeration problems for graphs

The Fibonacci number or $\sigma$-index of a graph is defined as the number of independent vertex subsets. For molecular graphs, this index has several applications in combinatorial chemistry. The talk is based on a joint work of Knopfmacher, Tichy, Ziegler and the speaker. It deals with enumeration problems concerning this graph-theoretical index, such as characterizing graphs of small or large index or calculating the average index of some given graph class. In particular, a special class of trees - the so-called ``star-like'' trees - will be discussed. This class of trees corresponds to partitions of natural numbers in a well-defined way. The main results include the fact that all trees with Fibonacci number $>2^{n-1}+5$ (where $n$ denotes the number of edges) are star-like and an asymptotic formula for the average Fibonacci number of a star-like tree.

Back to the Index