Properties of the Fibonacci-sum graph

2017/10/27 by Andrii Arman, Arman, Andrii, David S. Gunderson +3 · 1 voice
Computer Science · Mathematics · #05C75 #11B39 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.1710.10303

openalex publication_date 2017/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For each positive integer n, the Fibonacci-sum graph G_n on vertices 1,2,…,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.

Discussions

• I used gpt5.6-sol to help find a proof for this question. I also verified the proof in lean : https://theoremdb.org/statements/fib-problem-determinant-range/#lean-verification , which is why it took m [stackexchange, 12 points]

Related

• Some Properties of Fibonacci-Sum Set-Graphs
• Fibonacci Sumsets and the Gonality of Strip Graphs
• Fibonacci-run graphs I: basic properties
• Partial sums of the Gibonacci sequence
• Proofs For Progressively Generalized Fibonacci Identities Using Maximal Independent Sets of Tree Graphs