The Number of Quasi-Trees in Fans and Wheels

Abstract

We extend the classical relation between the $2n$-th Fibonacci number and the number of spanning trees of the $n$-fan graph to ribbon graphs.  More importantly, we establish a relation between the $n$-associated Mersenne number and the number of quasi trees of the $n$-wheel ribbon graph. The calculations are performed by computing the determinant of a matrix associated with ribbon graphs. These theorems are also proven using contraction and deletion in ribbon graphs. The results provide  neat and symmetric combinatorial interpretations of these well-known sequences. Furthermore, they are refined by giving two families of abelian groups whose orders are the  Fibonacci and associated Mersenne numbers.