Fibsum Graphs (2009)

Originator(s): Unknown presented by Gregory Puleo - REGS 2009)

Definitions: The Fibonacci sequence ⟨F⟩ is defined by F₁ = 1, F₂ = 1, and F_k = F_k-2 + F_k-1 for k > 2. For each positive integer n, the Fibonacci-sum graph of n, written G_n, is the graph with vertex set [n] such that i and j are adjacent if and only if i+j is a Fibonacci number.

Question 1: For which integers n does G_n have a spanning path?

Background: The original problem (Problem 2732 in J. Recreational Mathematics, Jan 2009) asked for a permutation of [34] such that the sum of adjacent numbers is a Fibonacci number. The current presentation casts the same problem in explicitly graph-theoretic terms. The problem is interesting because we seek a spanning path in a rather sparse graph, and there seems to be no particular reason to expect it to have a spanning path, although the Fibonacci numbers themselves form a (relatively short) path in it. (It is an induced path, since a+F_j=b and a<F_j-1 imply b<F_j+1.) Below we show G₃₄, with a spanning path in red.

Conjecture 1. If n is a Fibonacci number, then G_n has a spanning path.

Algorithm (Greedy Algorithm). Seek a spanning path in G_n by starting at vertex n and iteratively moving to the largest neighbor that has not yet been visited.

Conjecture 2. If n is a Fibonacci number, then the greedy algorithm finds a spanning path in G_n.

Comments: Conjecture 2 clearly implies Conjecture 1. The motivation for this greedy algorithm is that if n is a Fibonacci number, then n has degree 1 in G_n and must be an end of the path. Similarly, the large numbers tend to be vertices with small degree, and hence the algorithm visits them as soon as possible.

Fox and Kinnersley (REGS 2009) appear to have developed an algorithm that transforms a spanning path in G_Fk into a spanning path in G_Fk+1 (not the greedy algorithm given above). The details need to be worked out, but if this is true, then it establishes Conjecture 1.

Possibly the spanning path is unique. If so, then the Fox-Kinnersley approach (if correct) should also be able to decide whether Conjecture 2 is true. Snevily noted that the spanning path from 34 shown above alternates two odd numbers and two even numbers after the intial value. This is also true in G₈. Is it true whenever n is an even Fibonacci number? The parity patterns for the paths from other Fibonacci numbers seem more complicated.

Question 2: What graph-theoretic properties are satisfied by G_n for all n?

Comments: There is a "universal" infinite graph containing G_n for all n, since G_n-1 is obtained from G_n simply by deleting vertex n. Also G_n is 2-degenerate, since the highest (last) vertex in any induced subgraph has degree at most 2 in the subgraph.

Next, we show that G_n is bipartite. It suffices to prove this by induction on k for G_Fk. As vertices are added to G_Fk, the added vertex i has degree 1 for F_k+1 ≤ i ≤ (F_k+F_k+1)/2 (and for i=F_k+1). For (F_k+F_k+1)/2 < i ≤ F_k+1-1, vertex i has degree 2 when it arrives; the two neighbors of F_k+1-j are F_k+j and j. However, those two vertices have the common neighbor F_k-1-j. Hence F_k+j receives the color of j, and F_k+1-j receives the color of F_k-1-j, and the graph remains bipartite.

Since when a vertex x of degree 2 is added it is made adjacent to a leaf y and a neighbor of a neighbor of y, also G_n always remains connected and planar. Furthermore, the Fibonacci numbers are and remain cut-vertices. There is some sort of fractal behavior in the growth of the blocks.

What about spanning paths in G_n when n is not a Fibonnaci number? If G_Fk has a spanning path, then since F_k has degree 1 in it, also G_Fk-1 has a spanning path. Working the other direction, recall that for F_k+1≤n≤(F_k+F_k+1)/2, the vertices beginning with F_k are leaves in G_n, with one exception when F_k is even. In that case, F_k/2 remains a leaf from when it arrives until n=F_k+1-F_k/2. After (F_k+F_k+1)/2, the higher leaves disappear one by one. The consequence is that except for a few values around the Fibonacci numbers, G_n has at least three leaves and hence no spanning path.

These observations show that only a few numbers around each Fibonacci number remain to be settled. The values of n up to 52 such that G_n has a spanning path are 1,2,3,4,5,7,8,9,11,12,13,20,21,33,34. Now 35 fails because 17,34,35 are leaves, and then 34,35,36 all remain leaves until 53, which is the next possibility.

When n is not a Fibonacci number, there may be a spanning path in G_n that the greedy algorithm cannot find. For example, 5 and 4 are leaves in G₇, but the greedy algorithm does not start at either and hence cannot find the only spanning path, 5,3,2,6,7,1,4.

Question 3. Is there a nice generalization of Fibonacci-sum graphs to other recurrences?

Comment: The Lucas numbers satisfy the Fibonacci recurrence but with initial values 1 and 3 instead of 1 and 2. It seems likely that the Lucas-sum graphs share many properties with the Fibonacci-sum graphs.

Source Code:The Python script fibgraph.py generates Graphviz code for fibsum graphs. To use it, download the script and type

./fibgraph.py N

./fibshow N

chmod 700 fibgraph.py
chmod 700 fibshow
chmod 700 mfibshow