The Fibonacci number of generalized Petersen graphs
Stephan G. Wagner · The Fibonacci Quarterly · 2006
The Fibonacci number F(G) of a graph G is defined as the number of independent vertex subsets of G. It was introduced in a paper of Prodinger and Tichy in 1982. There, they also ask for a formula for the Fibonacci number of a generalized Petersen graph. The aim of the current paper is to solve this problem by deriving a recursion. It will be shown that the Fibonacci number of the generalized Petersen graph with 4n+2 vertices is asymptotically αn+1/2, where α = 5.6709364838 is an algebraic number of degree 5.