Counting Trees in a Certain Class of Graphs

1975/01/01 by D. J. Kleitman, Daniel J. Kleitman, B. Golden +1 · 1 citation
Computer Science · Physics and Astronomy · #Data Management and Algorithms #Graph Theory and Algorithms #Complex Network Analysis Techniques

paper · doi:10.1080/00029890.1975.11993767

Abstract

The number of trees contained in a certain class of graphs is obtained by a simple argument. The graphs can be represented by choosing the integers from 1 to n as vertices and connecting vertices whose difference mod n is one or two. The answer is n times the square of the nth Fibonacci number.

Cited by

• Chebyshev Recurrence Structures for Reduced Spectral Functions of Cyclic Circulant Graphs

Related

• Fibonacci Numbers in the Count of Spanning Trees
• Computing the tree number of a cut-outerplanar graph
• Counting of paths and the multiplicity of determinantal rings
• Forests of chord diagrams with a given number of trees
• Counting graphs with different numbers of spanning trees through the counting of prime partitions