No label defined (Q4028491)

[For the entire collection see Zbl 0747.00034.] In a graph \(G_ n\) with \(n\) vertices, they can be identified with the integers modulo \(n\). Several authors have considered circular graphs (or rotationally symmetric graphs), in which a rotation (adding, modulo \(n\), of a constant \(j\) to the vertices) induces a graph isomorphism. Such graphs have been proposed and implemented as architectures for fault-tolerant communications networks. A measure of the reliability of such a network is given by the number of spanning trees in the network. If some spanning tree of functioning communications links exists in a network, then any two ``nodes'' (vertices) can communicate. The more spanning trees in the graph, the higher the likelihood that a viable spanning tree remains after assorted link failures. In \textit{D. J. Kleitman} and \textit{B. Golden} [Am. Math. Mon. 82, 40-44 (1975; Zbl 0297.05123)], the authors consider the circulant graph on \(n\) vertices \(G_ n(1,2)\), where any two nodes share an edge exactly when their difference is \(\pm 1\) or \(\pm 2\) modulo \(n\). They give the following formula for \(N_ n(1,2)\), the number of spanning trees in this graph: \(N_ n(1,2)=n\cdot f^ 2_ n\), where \(f_ n\) is the \(n\)th term of the Fibonacci sequence. The authors' proof of the formula relies in an essential manner on properties of an embedding of the graph into a planar continuum. As a point of departure for this work, it would seem desirable to obtain this formula by an entirely combinatorial construction. Our new approach yields methods that apply to other classes of rotationally symmetric graphs. As an example, we give a recursion formula for \(N_ n(1,3)\), where in the graph \(G_ n(1,3)\), vertices \(i\) and \(j\) have a common edge if and only if \(| i-j|=1\) or \(=3\), modulo \(n\).