Joe DeMaio^a , John Jacobson^b

^aDepartment of Mathematics, Kennesaw State University, USA ^bMoxie, Atlanta, Georgia, USA

jdemaio@kennesaw.edu, johnjacobson8128@gmail.com

In 1982, Prodinger and Tichy defined the Fibonacci number of a graph G to be the number of independent sets of the graph G. They did so since the Fibonacci number of the path graph Pⁿ is the Fibonacci number Fn+2 and the Fibonacci number of the cycle graph Cⁿ is the Lucas number Ln. The tadpole graph Tn,k is the graph created by concatenating Cⁿ and P^k with an edge from any vertex of Cⁿ to a pendant of P^k for integers n = 3 and k = 0. This paper establishes formulae and identities for the Fibonacci number of the tadpole graph via algebraic and combinatorial methods.

Keywords: independent sets; Fibonacci sequence; cycles; paths

Mathematics Subject Classification : 05C69

1. Introduction

Given a graph G = (V, E), a set S ⊆ V is an independent set of vertices if no two vertices in S are adjacent. In our illustrations, we indicate membership in an independent set S by shading the vertices in S. Let the set of all independent sets of a graph G be denoted by I (G) and let i(G) = |I (G)|. Note that ∅ ∈ I (G). The path graph, Pn, consists of the vertex set V = {1, 2, . . . , n} and the edge set E = {{1, 2} , {2, 3} , . . . , {n − 1, n}}. The cycle graph, Cn, is the path graph, Pn,with the additional edge {1, n}.

Table 1 shows initial Fibonacci and Lucas numbers. In 1982, Prodinger and Tichy defined the Fibonacci number of a graph G, i(G), to be the number of independent sets (including the empty

Received: 20 June 2014, Revised: 05 August 2014, Accepted: 15 September 2014.

Figure 1. Independent sets of P1; P2; P3; and P4.

Figure 2. Independent sets of C³ and C4.

set) of the graph G [5]. They did so because the Fibonacci number of the path graph Pⁿ is the Fibonacci number Fn+2, and the Fibonacci number of the cycle graph Cⁿ is the Lucas number Ln.

Table 1: Initial values of the Fibonacci and Lucas sequences

In [1], the authors of this paper use these graphs to combinatorially derive identities relating Fibonacci and Lucas numbers.

Example 1. Lⁿ = Fn−¹ + Fn+1 for positive integers n ≥ 3.

Proof. On the one hand we know that i(Cn) = Ln. On the other hand, vertex 1 is either a member of the independent set or it is not. If not, then any independent set from Pn−1, formed by vertices 2 through n, can be selected in i(Pn−1) ways. If in the set, then the remaining members can be selected in i(Pn−3) ways from the path formed by vertices 3 through n − 1, since vertices 2 and n can not be selected. Hence, Lⁿ = i(Cn) = i(Pn−3) + i(Pn−1) = Fn−¹ + Fn+1.

The Fibonacci sequence and the Lucas sequence are famous examples of the more general form called the Gibonacci sequence [3]. For integers G⁰ = a and G¹ = b, the Gibonacci sequence is defined recursively as Gⁿ = Gn−¹ + Gn−² for positive integers n ≥ 2. Do other graphs exist whose Fibonacci numbers form a Gibonacci sequence?

The tadpole graph, Tn,k, is the graph created by concatenating Cⁿ and P^k with an edge from any vertex of Cⁿ to a pendent of P^k for integers n ≥ 3 and k ≥ 0. For ease of reference we label the vertices of the cycle c1, ..., cn, the vertices of the path p1, ..., p^k where c¹ is adjacent to p1.

Figure 3. The Tadpole Graph Tn,k.

Example 2. Independent sets on T3,²

Figure 4. T3,2.

\[I(T_{3,2}) = \{\emptyset, \{c_1\}, \{c_2\}, \{c_3\}, \{p_1\}, \{p_2\}, \{c_1, p_2\}, \{c_2, p_1\}, \{c_2, p_2\}, \{c_3, p_1\}, \{c_3, p_2\}\}\]

Theorem 1.1. i(Tn,k) = i(Tn,k−1) + i(Tn,k−2).

Proof. We show that I (Tn,k) = I (Tn,k−1)∪I (Tn,k−2) where I (Tn,k−1)∩I (Tn,k−2) = ∅. Partition I (Tn,k) into two disjoint subsets: sets where p^k is shaded and sets where p^k is not shaded. For every independent set in I (Tn,k−2), add an unshaded vertex pk−¹ followed by a shaded vertex p^k to the end of the path graph. For every independent set in I (Tn,k−1), add an unshaded vertex p^k to the end of the path graph. Therefore, i(Tn,k) = i(Tn,k−1) + i(Tn,k−2).

Theorem 1.2. \[i(T_{n,k}) = i(T_{n-1,k}) + i(T_{n-2,k})\].

Proof. Again, we show that I (Tn,k) = I (Tn−1,k) ∪ I (Tn−2,k) where I (Tn−1,k) ∩ I (Tn−2,k) = ∅. Label any three consecutive vertices of Tn,k of degree two from the cycle as n − 1, n and 1. For every independent set in I (Tn−2,k), if vertex 1 is shaded (then vertex n − 2 is not shaded), insert a shaded vertex n−1 and an unshaded vertex n, thus creating all independent sets of Tn,k that include both 1 and n−1. If vertex 1 is not shaded, then insert a shaded vertex n and unshaded vertex n−1 creating all independent sets where vertex n is shaded. For every independent set in I (Tn−1,k), insert an unshaded vertex n which finally creates all independent sets where either 1 or n − 1 is shaded or none of n − 1, n and 1 are shaded. Therefore, i(Tn,k) = i(Tn−1,k) + i(Tn−2,k).

It is immediate that i(Tn,0) = Lⁿ since Tn,⁰ ∼= Cn. Computing i(T3,2) = 11 and i(T4,1) = 12 allows us to effortlessly fill in the following table since by Theorems 1.1 and 1.2, every row and column forms a Gibonacci sequence.

Table 2: Fibonacci Numbers for the Tadpole Graph, Tn,k

It is easy to directly compute the Fibonacci number of any Tadpole graph.

Theorem 1.3. \[i(T_{n,k}) = L_{n+k} + F_{n-3}F_k\].

Proof. We proceed with two base cases and strong induction on k. Suppose k = 0. Then i(Tn,0) = i(Cn) = Ln+Fn−3F⁰ = Ln. For k = 1, combinatorially, i(Tn,1) = i(Cn)+i(Pn−1) = Ln+Fn+1. Now algebraically,

\[L_n + F_{n+1} = L_{n+1} - L_{n-1} + F_n + F_{n-1}\]\[= L_{n+1} - F_{n-2} + F_{n-1}\]\[= L_{n+1} + F_{n-3}F_1.\]

Finally, for general k ≥ 2,

\[i(T_{n,k+1}) = i(T_{n,k}) + i(T_{n,k-1})\] \[= L_{n+k} + F_{n-3}F_k + L_{n+k-1} + F_{n-3}F_{k-1}\] \[= L_{n+k+1} + F_{n-3}F_{k+1}.\]

Theorem 1.4. For n ≥ 3 and k ≥ 0,

1. \[L_{n+k} = F_{n-1}F_{k+1} + F_{n+1}F_{k+2} - F_{n-3}F_k;\]

2. \[L_{n+k} = F_{n+1}F_k + L_nF_{k+1} - F_{n-3}F_k;\]

3. \[L_{n+k} = F_{n-1}F_{k+2} + F_{n+k+1} - F_{n-3}F_k\].

Proof. For 1, we know that there are Ln+^k + Fn−3F^k independent sets on the tadpole graph Tn,k. Now we partition I (Tn,k) into two disjoint sets: sets that contain c¹ and sets that do not. If c¹ is included in the independent set then c2, cⁿ and p¹ are not. Hence, there are i(Pn−3)i(Pk−1) = Fn−1Fk+1 such sets. If c¹ is not included in the independent set then there are i(Pn−1)i(Pk) = Fn+1Fk+2 such sets. So, Ln+^k + Fn−3F^k = Fn−1Fk+1 + Fn+1Fk+2 and the result follows.

For 2, we partition I (Tn,k) into two disjoint sets: sets that contain p¹ and sets that do not. If p¹ is included in the independent set then c1,and p² are not. Hence, there are i(Pn−1)i(Pk−2) = Fn+1F^k such sets. If p¹ is not included in the independent set then there are i(Cn)i(Pk−1) = LnFk+1 such sets. So Ln+^k + Fn−3F^k = Fn+1F^k + LnFk+1 and the result follows.

For 3, we partition I (Tn,k) into two disjoint sets: sets that contain cⁿ and sets that do not. If cⁿ is included in the independent set then c¹ and cn−¹ are not. Hence, there are i(Pn−3)i(Pk) = Fn−1Fk+2 such sets. If cⁿ is not included in the independent set then there are i(Pn−1+k) = Fn+k+1 such sets. So, Ln+^k + Fn−3F^k = Fn−1Fk+2 + Fn+k+1 and the result follows.

2. Tadpole Triangle

We turn Table 2 into a triangular array where the (n, k) entry for n ≥ 3 and k ≥ 0 will be denoted tn,k. Row n will represent the class of tadpole graphs with a total of n vertices. As the value of k increases by 1 through each row of the triangle, the cycle subgraph shrinks by one vertex and the length of the path subgraph increases by one. Thus, tn,k represents the number of independent sets on the Tadpole graph with n vertices with a path of length k (and thus, a cycle of length n − k). Hence, tn,k = i(Tn−k,k). By Theorem 1.3, tn,k = Lⁿ + Fn−k−3Fk.

Table 3: The Triangular Array of Fibonacci Numbers of the Tadpole Graph

As noted before, tn,⁰ = i(Tn,0) = Ln. Casual observation seems to indicate the rows the tadpole triangle are symmetric.

Theorem 2.1. tn,k = tn,n−k−³

Proof. Theorem 1.3 provides a quick, algebraic proof of the symmetry of rows since \[t_{n,n-k-3} = i(T_{k+3,n-k-3}) = L_n + F_k F_{n-k-3} = i(T_{n-k,k}) = t_{n,k}\].

Proof. For a combinatorial proof of the symmetry in rows, consider c² in both Tk+3,n−k−³ and Tn−k,k. As before, we partition the tadpole graphs into two disjoint sets: those that contain c² and those that do not. Both tadpole graphs contain n vertices. Thus, the number of independent sets that do not contain c² in each tadpole graph is the number of independent sets on the path with

n − 1 vertices. Independent sets that contain c2, do not contain c1. This decomposes the tadpole graph into two disjoint paths. For both tadpole graphs, disjoint paths of length k and n − k − 3 are created. Both tadpole graphs lead to the same decomposition and tn,k = tn,n−k−3.

Theorem 2.2. \[t_{n,k+1} - t_{n,k} = (-1)^k F_{n-2k-4}\] for \(0 \le k \le \lfloor \frac{n-3}{2} \rfloor\).

Proof. Algebraically,

\[t_{n,k+1} - t_{n,k} = L_n + F_{n-k-4}F_{k+1} - (L_n + F_{n-k-3}F_k)\]
= \(F_{n-k-4}F_{k+1} - F_{n-k-3}F_k\)
= \((-1)^k F_{n-2k-4}\) by d'Ocagne's Identity.

Proof. Combinatorially we proceed by initially considering the mapping

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

from I(Tn−k,k) to I(Tn−k−1,k+1) as illustrated in Figure 5. The identity mapping pairs together most independent sets but encounters obvious problems since independent sets in I(Tn−k,k) that contain both c² and cn−^k do not map to I(Tn−k−1,k+1), and independent sets in I(Tn−k−1,k+1) that contain both c1and cn−^k have no pre-image in I(Tn−k,k). If c² and cn−^k are both in the independent set, then remove c² from the independent set while including c¹ to create an independent set in I(Tn−k−1,k+1) to upgrade the identity mapping to Ψ (S). We now have two subtle issues which provide the value of tn,k+1 − tn,k. Independent sets in I(Tn−k,k) that contain the subset {p1,c2,cn−k} have no image. There are i(Pn−k−5)i(Pk−2) = Fn−k−3F^k such sets. Independent sets in I(Tn−k−1,k+1) that contain the subset {c1,c2,cn−k} have no pre-image. There are i(Pn−k−6)i(Pk−1) = Fn−k−4Fk+1 such sets. Once again, tn,k+1−tn,k = Fn−k−4Fk+1−Fn−k−3F^k = (−1)^kFn−2k−4.

Figure 5. Mapping I(Tn−k,k) to I(Tn−k−1,k+1).

Theorem 2.3. \[\sum_{k=0}^{n-3} (-1)^k t_{n,k} = \begin{cases} 0 \text{ for even } n \\ 2F_n \text{ for odd } n. \end{cases}\]

Proof. For even n the result is trivial due to the symmetry of row values. For odd n, we proceed by induction. Base cases abound from Table 3. Assume n is odd and nP−3 k=0 (−1)^k tn,k = 2Fn. Moving on to the next odd value we consider

\[\begin{split} \sum_{k=0}^{n-1} (-1)^k t_{n+2,k} &= \left(\sum_{k=0}^{n-3} (-1)^k t_{n+2,k}\right) + (-1)^{n-2} t_{n+2,n-2} + (-1)^{n-1} t_{n+2,n-1} \\ &= \sum_{k=0}^{n-3} (-1)^k t_{n+2,k} - t_{n+2,n-2} + L_{n+2} \\ &= \left(\sum_{k=0}^{n-3} (-1)^k [t_{n,k} + t_{n+1,k}]\right) - L_{n+2} + F_{n+2-4} + L_{n+2} \\ &= \sum_{k=0}^{n-3} (-1)^k t_{n,k} + (-1)^k t_{n+1,k} - L_{n+2} - F_{n-2} + L_{n+2} \\ &= \left(\sum_{k=0}^{n-3} (-1)^k t_{n,k}\right) + \left(\sum_{k=0}^{n-2} (-1)^k t_{n+1,k}\right) + t_{n+1,n-2} - L_{n+2} - F_{n-2} + L_{n+2} \\ &= 2F_n + 0 + t_{n+1,n-2} - F_{n-2} = 2F_n + L_{n+1} - F_{n-2} \\ &= 3F_n + F_{n+2} - F_{n-2} = 2F_n + F_{n-1} + F_{n+2} \\ &= F_n + F_{n+1} + F_{n+2} = 2F_{n+2} \end{split}\]

Theorem 2.4. The ratio of consecutive row sums converges to the golden ratio φ.

Proof. The sum of row n can be written as

\[\sum_{k=0}^{n-3} t_{n,k} = \sum_{k=0}^{n-3} (L_n + F_{n-k-3}F_k)\] \[= \sum_{k=0}^{n-3} L_n + \sum_{k=0}^{n-3} F_{n-k-3}F_k\] \[= (n-2)L_n + \frac{(n-3)L_{n-3} - F_{n-3}}{5}\]

Now,

\[\lim_{n \to \infty} \frac{(n+1-2)L_{n+1} + \frac{(n+1-3)L_{n+1-3} - F_{n+1-3}}{5}}{(n-2)L_n + \frac{(n-3)L_{n-3} - F_{n-3}}{5}}\] \[= \lim_{n \to \infty} \frac{(n-1)L_{n+1} + \frac{(n-2)L_{n-2} - F_{n-2}}{5}}{(n-2)L_n + \frac{(n-3)L_{n-3} - F_{n-3}}{5}}\] \[= \lim_{n \to \infty} \frac{nL_{n+1} + nL_{n-2} - F_{n-2}}{nL_n + nL_{n-3} - F_{n-3}}\] \[= \lim_{n \to \infty} \frac{L_{n+1} + L_{n-2}}{L_n + L_{n-3}}\] \[= \lim_{n \to \infty} \frac{L_n}{L_{n-1}} = \phi.\]

A perfect matching (or 1-factor) in a graph G = (V, E) is a subset S of edges of E such that every vertex in V is incident to exactly one edge in S. In [2], Gutman and Cyvin define the L-shaped graph, Lp,q, to be the graph with p + q + 1 copies of C⁴ as illustrated in Figure 6 by L2,1.

Figure 6. L2,1.

{{1, 2}, {3, 4}, {5, 6}, {7, 10}, {8, 9}}
{{1, 2}, {3, 4}, {5, 8}, {6, 9}, {7, 10}}
{{1, 2}, {3, 5}, {4, 6}, {7, 10}, {8, 9}}
{{1, 2}, {3, 4}, {5, 8}, {6, 7}, {9, 10}}
{{1, 3}, {2, 4}, {5, 6}, {8, 9}, {7, 10}}
{{1, 3}, {2, 4}, {5, 8}, {6, 7}, {9, 10}}
{{1, 3}, {2, 4}, {5, 8}, {6, 9}, {7, 10}}

Table 4: The seven perfect matchings of L2,¹

They show that the number of perfect matchings in Lp,q is Fp+q+2 + Fp+1Fq+1. These values correspond to the columns of the tadpole triangle. This correspondence provides a quick proof of the symmetry of rows of the tadpole triangle since Lp,q ≈ Lq,p. We number columns starting with the center at i = 0.

Theorem 2.5. The number of perfect matchings in Lp,q is given by tp+q+1,q−1, the p th entry in columns ±(p − q).

Proof. Since the tadpole triangle is symmetric we can assume that p ≥ q. By Theorem 1.3,

\[\begin{split} t_{p+q+1,q-1} &= L_{p+q+1} + F_{p-1}F_{q-1} \\ &= F_{p+q+2} + F_{p+q} + F_{p-1}F_{q-1} \\ &= F_{p+q+2} + (F_{p+1}F_{q+1} - F_{p-1}F_{q-1}) + F_{p-1}F_{q-1} \\ &= F_{p+q+2} + F_{p+1}F_{q+1}. \end{split}\]

3. Future Work

In [4], Pederson and Vestergaard show that for every unicyclic graph G of order n, Lⁿ ≤ i(G) ≤ 3 × 2 ⁿ−³ + 1. Furthermore they show that the minimum bound is realized only for Tn,⁰ ≈ Cⁿ and T3,n−3. The maximum bound occurs only for C⁴ and the graph with n−3 pendants adjacent to the same vertex of C3. The technique of this paper can be used to precisely determine the Fibonacci number of many classes of unicyclic graphs.

Acknowledgement

The authors thank programs at Kennesaw State University and Brigham Young University for travel support when presenting this work at the Joint Mathematics Meetings in 2014 and the Forty-Fifth Southeastern International Conference on Combinatorics, Graph Theory, and Computing. At KSU, The Center for Excellence in Teaching and Learning's URCA program and at BYU, The Center for Undergraduate Research in Mathematics both encourage the inclusion of undergraduate students in faculty research and dissemination of results at professional conferences.

References

• [1] J. DeMaio and J. Jacobson, Fibonacci and Lucas identities via graphs, Springer Proceedings in Mathematics & Statistics: Topics from the 8th Annual UNCG Regional Mathematics and Statistics Conference,(pp. 85–92). Springer New York.
• [2] I. Gutman and S. Cyvin, A result on 1-factors related to Fibonacci numbers, Fibonacci Quarterly 28(1) (1990), 81–84.
• [3] T. Koshy, Fibonacci and Lucas numbers with applications, Wiley-Interscience, New York, 2001.
• [4] A.S. Pederson and P.D. Vestergaard, The number of independent sets in unicyclic graphs, Discrete Applied Mathematics 152 (2005), 246–256
• [5] H. Prodinger and R. Tichy, Fibonacci numbers of graphs, Fibonacci Quarterly 20(1) (1982), 16–21.