Properties of the Fibonacci-sum graph

Abstract

For each positive integer \(n\), the Fibonacci-sum graph \(G_n\) on vertices \(1,2,\ldots,n\) is defined by two vertices forming an edge if and only if they sum to a Fibonacci number. It is known that each \(G_n\) is bipartite, and all Hamiltonian paths in each \(G_n\) have been classified. In this paper, it is shown that each \(G_n\) has at most one non-trivial automorphism, which is given explicitly. Other properties of \(G_n\) are also found, including the degree sequence, the treewidth, the nature of the bipartition, and that \(G_n\) is outerplanar.