Fibonacci Numbers of Generalized Zykov Sums

César Bautista-Ramos and Carlos Guillén-Galván Facultad de Ciencias de la Computación Benemérita Universidad Autónoma de Puebla 14 Sur y Av. San Claudio, Edif. 104C, 303 Puebla, Pue. 72570 Mexico

                      bautista@cs.buap.mx
                      cguillen@cs.buap.mx

Abstract

We show that counting independent sets in several families of graphs can be done within the framework of generalized Zykov sums by using the transfer matrix method. Then we calculate the generating function of the number of independent sets for families of generalized Zykov sums. We include many interesting particular cases (Petersen graphs, generalized Möbius ladders, carbon nanotube graphs, among others).

1 Introduction

The Fibonacci number F (G) of a graph G was introduced by Prodinger and Tichy [15] and is defined as the number of independent sets of G. In combinatorial chemistry this number is also known as the Merrifield-Simmons index [11, 12]. Prodinger and Tichy calculated F (G) recursively by paying attention to whether certain vertices appear or not in what they call the usual recursion argument. Such binary occurrence problem is formalized, in this paper, in the transfer matrix method [2, 6, 7, 10].

Our goal is to show how to count independent sets in graphs with some pattern structure. The structure we are dealing with is a generalization of the Zykov sum of graphs (also known as the graph join). Let us recall that the Zykov sum is the graph obtained from the disjoint union of two graphs G_{1}, G_{2} by joining each vertex of G_{1} with each vertex of G_{2}. This join is just a particular case of a relation set between the vertices of G_{1} and G_{2}. In this work, we generalize Zykov sums by joining vertices only when they belong to a given relation set. We call these open or closed Zykov sums (the formal definitions are introduced in the next section). It is almost trivial to show that the independent sets of G_{1} and G_{2} give rise to a new independent set in their open or closed Zykov sum, unless their vertices belong to the relation (see Theorem 5). Such binary information, whether vertices are related or not, is stored in a matrix known as the transfer matrix [2, 6, 7, 10]. The transfer matrix is particularly useful for graphs that can be written as a repetitive pattern of open or closed Zykov sums. Then, the product of the transfer matrices stores information about the number of independent sets. We show that the usual matrix product gives the number of independent set in graphs that are some kind of strip, while the Hadamard product of matrices is for closing such strips in order to form some type of circular structure, like cycles or tori.

To illustrate our methods we use several families of graphs having a repetitive pattern of generalized Zykov sums which include paths, cycles, grids, cylinders, tori, Möbius ladders, and generalized Petersen graphs, among others. Additional examples are honeycomb tubes (nanotube graphs) and honeycomb torus graphs (nanotorus graphs) which are particularly interesting because they appear in parallel computing architectures [18] and nanotechnology [14].

There are other works dealing with the Fibonacci number F (G) when G has a different structure from those studied here; for instance, trees [11], regular graphs [3, 17, 21], unicyclic graphs [13], graphs with small maximum degree [9], graphs with a given number of vertices and edges [4], and graphs with a given minimum degree [8]. However, these works deal with estimations for F (G), in contrast to our work, which is interested mainly in exact formulas for F (G) when G is an open or closed Zykov sum. Exact formulas for Fibonacci numbers of graph are also the concern of Golin, Leung, Wang, and Yong [10], Euler [7], Prodinger and Tichy [15], Warner [20], Engel [6], Calkin and Wilf [2], Burnstein, Kitaev, and Mansour [1], among others. However, there are some errors in [1], as we show in Section 5.

This paper is organized as follows: In Section 2 we introduce the basic definitions and some examples; in Section 3 we give the related theorems for counting independent sets along with some examples; in Section 4, we calculate the generating function of the Fibonacci numbers for some families of open and closed Zykov sums. Finally, in Section 5, we describe more examples, among them (almost) regular graphs [1] where we also show some counterexamples to the calculations in [1].

2 Definitions

In this paper we deal only with multigraphs [5]. However, since we are interested in the number of independent sets, the multiple edges are irrelevant, but the loops are not. Therefore, by a graph, we refer to a multigraph without multiple edges but, perhaps, with loops. For such a graph G, we denote the sets of vertices and edges of G as V (G) and E(G), respectively. We are mainly interested in binary relations between graphs because they describe a basic building block for patterns in families of certain graphs. These relations lead to a couple of sums of graphs: closed and open Zykov sums denoted +_{R}, ⊕_{R} respectively. Both are defined below.

Definition 1. Let ⊎ be the disjoint union operator. Let G_{1}, …, G_{n} be a collection of graphs and R_{1}, …, R_{n−1} be a collection of relations such that each R_{i} is a relation set from V (G_{i}) to V (G_{i+1}), i = 1, …, n − 1 . Let E_{i} = {{v, w} ⊆ V (G_{i}) ⊎ V (G_{i+1}) | v ∈ V (G_{i}), w ∈ V (G_{i+1}) with vR_{i}w}, i = 1, …, n−1. We define a new graph G_{1} +_{R_{1}} ⋯+_{R_{n−1}} G_{n} as follows:

V (G_{1} +_{R_{1}} ⋯ +_{R_{n−1}} G_{n}) = V (G_{1}) ⊎ ⋯ ⊎ V (G_{n})

and

E(G_{1} +_{R_{1}} ⋯ +_{R_{n−1}} G_{n}) = E(G_{1}) ⊎ ⋯ ⊎ E(G_{n}) ⊎ E_{1} ⊎ ⋯ ⊎ E_{n−1}.

We call G_{1} +_{R_{1}} ⋯ +_{R_{n−1}} G_{n} an open Zykov sum .

If we have an additional relation R_{n} from V (G_{n}) to V (G_{1}), we define an extra graph G_{1} ⊕_{R_{1}} ⋯ ⊕_{R_{n−1}} G_{n} ⊕_{R_{n}} G_{1} as

V (G_{1} ⊕_{R_{1}} ⋯ ⊕_{R_{n−1}} G_{n} ⊕_{R_{n}} G_{1}) = V (G_{1}) ⊎ ⋯ ⊎ V (G_{n})

and

E(G_{1} ⊕_{R_{1}} ⋯ ⊕_{R_{n−1}} G_{n} ⊕_{R_{n}} G_{1}) = E(G_{1}) ⊎ ⋯ ⊎ E(G_{n}) ⊎ E_{1} ⊎ ⋯ ⊎ E_{n}

where E_{n} = {{u, v} : u ∈ V (G_{n}) and v ∈ V (G_{1}) with uR_{n}v}. We call G_{1} ⊕_{R_{1}} ⋯ ⊕_{R_{n−1}} G_{n} ⊕_{R_{n}} G_{1} a closed Zykov sum .

In the following section, we present several well known families of graphs that can be generated from Zykov sums.

2.1 Examples

Let C_{n} be the n-cycle graph with V (C_{n}) = {0, 1, …, n − 1} and E(C_{n}) = {{0, 1}, …, {n − 2, n − 1}, {n − 1, 0}}, where n = 1, 2, …

Platonic graphs. The platonic graphs are made of the vertices and edges of the five platonic solids. They can be constructed from open Zykov sums as is shown in Table 1. Note that the relations used are sometimes functions, and if not, the inverse relation is a function, except in the icosahedron case, where neither R_{1}^{±1} nor R_{2}^{±1} is a function.

Hypercubes. Let Q_{0} be the graph with vertex set given by the singleton set {v} and empty set of edges. Then the hypercubes Q_{n} can be defined recursively by Q_{n+1} = Q_{n} +_{Id_{n}} Q_{n}, n ≥ 0 where Id_{n} is the identity map on V (Q_{n}).

Paths. Let P_{0} be the singleton graph, where V (P_{0}) = {v_{0}} and E(P_{0}) = ∅. Let Id : {v_{0}} → {v_{0}} be the identity map. Then

P_{n} = P_{0} +_{Id} P_{0} +_{Id} ⋯ +_{Id} P_{0}

is the path graph of length n − 1, where P_{0} appears n times.

Graph name Zykov sum  Relation
Tetrahedral C_{1} +_{R} C_{3}  R = {(0, 0), (0, 1), (0, 2)}
Octahedral C_{3} +_{R} C_{3} R = {(0, 0), (0, 2), (1, 1), (1, 0),
(2, 2), (2, 1)}
Cube C_{4} +_{Id} C_{4} Id identity map on V (C_{4})
Icosahedral  C_{3} +_{R_{1}} C_{6} +_{R_{2}} C_{3} R_{1} = {(0, 0), (0, 1), (0, 2), (1, 2),
(1, 3), (1, 4), (2, 4), (2, 5), (2, 0)}
R_{2} = {(0, 0), (1, 0), (1, 1), (2, 1),
(3, 1), (3, 2), (4, 2), (5, 2), (5, 0)}
Dodecahedral C_{5} +_{R_{1}} C_{10} +_{R_{2}^{−1}} C_{5} R_{1}, R_{2} : V (C_{5}) → V (C_{10})
R_{1}(i) = 2i, R_{2}(i) = 2i + 1

Table 1: The platonic graphs as open Zykov sums. The graphs C_{n} are the n-cycle graphs

Grids, cylinders and tori. The grid G_{n,m} is defined by V (G_{n,m}) = {(i, j) : 1 ≤ i ≤ n, 1 ≤ j ≤ m} and E(G_{n,m}) = {{(i, j), (u, v)} : |i − u| + |j − v| = 1}. Then

G_{n,m} = P_{n} +_{Id} P_{n} +_{Id} ⋯ +_{Id} P_{n}  (1)

where the path P_{n} appears m times and Id is the identity function on V (P_{n}).

Now, let C_{n} be the n-cycle graph and Id the identity map on V (C_{n}). The cylinder n×m, as an open Zykov sum, is

C_{n,m} = C_{n} +_{Id} C_{n} +_{Id} ⋯ +_{Id} C_{n}

where C_{n} appears m times. On the other hand, the closed Zykov sum

T_{n,m} = C_{n} ⊕_{Id} C_{n} ⊕_{Id} ⋯ ⊕_{Id} C_{n}

is the torus n × m, where C_{n} appears m + 1 times. Note that in the Zykov sum T_{n,m}, the first and last terms have been identified by definition (see Definition 1).

3 Counting independent sets

In order to count independent sets, we are using the transfer matrix method [2, 6, 7, 10], which is based upon a perpendicularity concept. Following this idea, we propose a new inner product defined with the help of the relation set given in a Zykov sum.

Definition 2. Let B = {0, 1} and let G, H be a pair of graphs. Let B^{V (G)} be the cartesian product ∏_{v∈V (G)} B_{v}, where each B_{v} = B; similarly for B^{V (H)}. Let R be a relation from V (G) to V (H). For any a ∈ B^{V (G)}, b ∈ B^{V (H)} we define

⟨a|b⟩_{R} = ∑_{\begin{matrix}v,w \\ vRw \end{matrix}} π_{v}(a)π_{w}(b) ∈ ℕ

where π_{v} : B^{V (G)} → B_{v} = B, π_{w} : B^{V (H)} → B_{w} = B are the canonical projections.

Let 2^{V (G)} be the power set of V (G). There exists a unique bijection Ψ_{G} : 2^{V (G)} → B^{V (G)} such that

π_{v}Ψ_{G}(A) = χ_{A}(v), ∀v ∈ V (G), ∀A ⊂ V (G)  (2)

where χ_{A} is the characteristic function of the set A.

The following lemma translates the concept of independent set in Zykov sums into perpendicularity.

Lemma 3. Let G, H be a pair of graphs and R be a relation from V (G) to V (H). If A, B are independent sets of G, H respectively, then A ⊎ B is an independent set of G +_{R} H if and only if ⟨Ψ_{G}(A)|Ψ_{H}(B)⟩_{R} = 0.

Proof. The disjoint union A ⊎ B is an independent set of G +_{R} H iff for any v ∈ V (G), w ∈ V (H), vRw implies {v, w} ⊄ A ⊎ B iff vRw implies χ_{A}(v)χ_{B}(w) = 0 iff

∑_{\begin{matrix}v,w \\ vRw \end{matrix}} π_{v}(Ψ_{G}(A))π_{w}(Ψ_{H}(B)) = 0

because of (2).

The transfer matrix is defined below using the inner product relative to the Zykov sums.

Definition 4. 1. For a graph G, we denote the collection of independent sets of G with I_{G}; while F (G), called the Fibonacci number of G, stands for the cardinality of I_{G}, i.e., F (G) = |I_{G}|.

2. For any z ∈ ℕ we define

\overline{z} = \begin{cases}1, & if z = 0; \\ 0, & otherwise. \end{cases}

3. Let G, H be a pair of graphs and R be a relation from V (G) to V (H). The function

T_{G,H}^{R} : I_{G} × I_{H} → B, T_{G,H}^{R}(A, B) = \overline{⟨Ψ_{G}(A)|Ψ_{H}(B)⟩_{R}}

is called the transfer matrix of G +_{R} H.

Note that for any z_{1}, z_{2} ∈ ℕ, \overline{z_{1} + z_{2}} = \overline{z_{1}} \overline{z_{2}}. In the following Theorems 5 and 6, we show how to calculate the Fibonacci number of open and closed Zykov sums.

Theorem 5. Let G, H be a pair of graphs and R be a relation from V (G) to V (H). Then

1.

F (G +_{R} H) = ∑_{A∈I_{G},B∈I_{H}} T_{G,H}^{R}(A, B)

where T_{G,H}^{R} is the transfer matrix of G +_{R} H.

2. If G = H,

F (G ⊕_{R} G) = ∑_{A∈I_{G}} T_{G,G}^{R}(A, A)

where T_{G,G}^{R} is the transfer matrix of G +_{R} G.

Proof. 1. We have that if J ∈ I_{G+_{R}H} then there exist A ∈ I_{G} and B ∈ I_{H} such that J = A ⊎ B. Now, use Lemma 3.

2. We have that J ∈ I_{G⊕_{R}G} iff J ∈ I_{G} and ⟨Ψ(J)|Ψ(J)⟩_{R} = 0.

Theorem 6. Let G, H, K be graphs, R be a relation from V (G) to V (H) and S be a relation from V (H) to V (K). Then,

F (G +_{R} H +_{S} K) = ∑_{A∈I_{G},C∈I_{K}} ∑_{B∈I_{H}} T_{G,H}^{R}(A, B)T_{H,K}^{S}(B, C).  (3)

Furthermore, if K = G, then

F (G ⊕_{R} H ⊕_{S} G) = ∑_{A∈I_{G},B∈I_{H}} T_{G,H}^{R}(A, B)T_{H,G}^{S}(B, A) .  (4)

Proof. We have that J ∈ I_{G+_{R}H+_{S}K} iff there exist A ∈ I_{G}, B ∈ I_{H}, C ∈ I_{K} such that J = A ⊎ B ⊎ C and, due to Lemma 3,

⟨Ψ_{G}(A)|Ψ_{H}(B)⟩_{R} + ⟨Ψ_{H}(B)|Ψ_{K}(C)⟩_{S} = 0

which is equivalent to

\overline{⟨Ψ_{G}(A)|Ψ_{H}(B)⟩_{R}} \overline{⟨Ψ_{H}(B)|Ψ_{K}(C)⟩_{S}} = 1

so

|I_{G+_{R}H+_{S}K}| = ∑_{\begin{matrix}A∈I_{G},B∈I_{H} \\ C∈I_{K} \end{matrix}} \overline{⟨Ψ_{G}(A)|Ψ_{H}(B)⟩_{R}} \overline{⟨Ψ_{H}(B)|Ψ_{K}(C)⟩_{S}}

from which (3) follows.

Similarly J ∈ I_{G⊕_{R}H⊕_{S}G} iff there exist A ∈ I_{G} and B ∈ I_{H} such that J = A ⊎ B and ⟨Ψ_{G}(A)|Ψ_{H}(B)⟩_{R} + ⟨Ψ_{H}(B)|Ψ_{G}(A)⟩_{S} = 0, since Lemma 3. Thus

\overline{⟨Ψ_{G}(A)|Ψ_{H}(B)⟩_{R}} \overline{⟨Ψ_{H}(B)|Ψ_{G}(A)⟩_{S}} = 1

which leads to

|I_{G⊕_{R}H⊕_{S}G}| = ∑_{A∈I_{G},B∈I_{H}} \overline{⟨Ψ_{G}(A)|Ψ_{H}(B)⟩_{R}} \overline{⟨Ψ_{H}(B)|Ψ_{G}(A)⟩_{S}} .

In fact, the transfer matrix is an actual matrix indexed by the cartesian product of independent sets I_{G} × I_{H}. We denote such matrix by

T_{G,H}^{R} = (T_{G,H}^{R}(A, B))_{A∈I_{G},B∈I_{H}}.

Note that T_{G,H}^{R} depends on the inner product which is denoted as a bracket. This notation is borrowed from the Dirac notation used mainly in quantum mechanics, where it has proved of great value. So, we are going to keep using this notation when we define, for any graph G, the column matrix full of 1’s indexed by the vertices of G which we denoted |G⟩, while ⟨G| is the transpose of |G⟩. Then, Theorem 6 ensures that

F (G + H + K) = ⟨G|T_{G,H}^{R}T_{H,K}^{S}|K⟩,  (5)

furthermore

F (G ⊕_{R} H ⊕_{S} G) = ⟨G|T_{G,H}^{R} ∗ (T_{H,G}^{S})^{t}|H⟩  (6)

where ∗ stands for the Hadamard matrix product and the superindex t indicates matrix transposition. Let us recall that the Hadamard matrix product A ∗ B of two matrices A = (a_{i,j}), B = (b_{i,j}) of the same dimensions is given by multiplying the corresponding entries together: A ∗ B = (a_{i,j}b_{i,j}). Also, note that we can write the right hand side of (6) as a standard matrix product as follows

F (G ⊕_{R} H ⊕_{S} G) = Tr (T_{G,H}^{R}T_{H,G}^{S})  (7)

where Tr denotes the matrix trace. However the formula in (6) is less difficult to calculate than (7), since the fastest known algorithms for computing the usual matrix product have complexity strictly greater than quadratic, which is the complexity of the Hadamard matrix product. Thus, the formula in (6) is useful for computer calculation.

A similar formula to (5) and (6), for a general graph, was found by Merrifield and Simmons [12, p. 209] using an exponential operator related to the annihilation and creation operators, instead of our transfer matrices and bra and ket vectors. However, said Merrifield-Simmons formula is not a convenient way to handle the Zykov sum structure.

With the aforementioned notation, the proof of Theorem 6 can be generalized in order to obtain:

Theorem 7. 1. The number of independent sets of G_{1} +_{R_{1}} G_{2} +_{R_{2}} ⋯ +_{R_{n−1}} G_{n} is the matrix product ⟨G_{1}|T_{G_{1},G_{2}}^{R_{1}} ⋯ T_{G_{n−1},G_{n}}^{R_{n−1}}|G_{n}⟩.

2. The number of independent sets of G_{1} ⊕_{R_{1}} G_{2} ⊕_{R_{2}} ⋯ ⊕_{R_{n−1}} G_{n} ⊕_{R_{n}} G_{1} is the matrix trace Tr(T_{G_{1},G_{2}}^{R_{1}} ⋯ T_{G_{n−1},G_{n}}^{R_{n−1}}T_{G_{n},G_{1}}^{R_{n}}).

Next, the Fibonacci numbers of two classical platonic solid graphs are calculated using Theorem 7. The remaining classical platonic solid cases are similar. Our goal here is to show that the concept of Zykov sum is an adequate framework for using the matrix transfer method for counting independent sets.

Throughout this paper, we calculate the transfer matrices after the lexicographic order in the cartesian product {0, 1}^{|V (G)|} induced by 0 < 1, for any given graph G.

Octahedral graph. Using the decomposition of the octahedral graph as the Zykov sum given in Table 1, we get the following matrices:

⟨C_{3}| = (1, 1, 1, 1), T_{C_{3},C_{3}}^{R} = (\begin{matrix}1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \end{matrix}) , |C_{3}⟩ = (\begin{matrix}1 \\ 1 \\ 1 \\ 1 \end{matrix}) .

Thus, from Theorem 7, the Fibonacci number of the octahedral graph is F (C_{3} +_{R} C_{3}) = ⟨C_{3}|T_{C_{3},C_{3}}^{R}|C_{3}⟩ = 10.

Dodecahedral graph. From Table 1, we get that the dodecahedral graph G has Fibonacci number F (G) = ⟨C_{5}|T_{C_{5},C_{10}}^{R_{1}} (T_{C_{5},C_{10}}^{R_{2}})^{t} |C_{5}⟩ = 5, 828, where

T_{C_{5},C_{10}}^{R_{1}} (T_{C_{5},C_{10}}^{R_{2}})^{t} = ( \begin{matrix}123 & 89 & 89 & 89 & 65 & 89 & 65 & 65 & 89 & 65 & 65 \\ 89 & 55 & 63 & 64 & 40 & 63 & 39 & 45 & 55 & 39 & 40 \\ 89 & 55 & 55 & 63 & 39 & 64 & 40 & 40 & 63 & 39 & 45 \\ 89 & 63 & 55 & 55 & 39 & 63 & 45 & 39 & 64 & 40 & 40 \\ 65 & 39 & 39 & 40 & 24 & 45 & 27 & 27 & 40 & 24 & 25 \\ 89 & 64 & 63 & 55 & 40 & 55 & 40 & 39 & 63 & 45 & 39 \\ 65 & 40 & 45 & 40 & 25 & 39 & 24 & 27 & 39 & 27 & 24 \\ 65 & 40 & 39 & 39 & 24 & 40 & 25 & 24 & 45 & 27 & 27 \\ 89 & 63 & 64 & 63 & 45 & 55 & 39 & 40 & 55 & 40 & 39 \\ 65 & 39 & 40 & 45 & 27 & 40 & 24 & 25 & 39 & 24 & 27 \\ 65 & 45 & 40 & 39 & 27 & 39 & 27 & 24 & 40 & 25 & 24 \end{matrix} ) .

4 The series of independent sets

In this section, we study the generating function of sequences of Fibonacci numbers for families of graphs determined by Zykov sums which are structures defined by repeating a fixed pattern of relations.

In the following, we are assuming that G is a family (G_{i})_{i∈ℕ} of graphs.

Definition 8. We call the infinite series

F_{G}(x) = F (G_{0}) + F (G_{1})x + F (G_{2})x^{2} + ⋯  (8)

the Fibonacci series of G.

The following families, which contain repetitive patterns of open and closed Zykov sums, include many interesting cases such as grids, tori, cylinders [2, 7, 10] and so on.

Definition 9. Let G = (G_{n})_{n≥0} be a family of graphs. We call G a family of:

1. Strip graphs if there exists a graph G such that G_{0} = G, G_{1} = G +_{R} G, G_{2} = G +_{R} G +_{R} G, ….

2. Ring graphs if there exists a graph G such that G_{0} = G, G_{1} = G ⊕_{S} G, G_{2} = G ⊕_{R} G ⊕_{S} G, G_{3} = G ⊕_{R} G ⊕_{R} G ⊕_{S} G, …. In such a case G +_{S} G is called the skewing of G.

3. Alternating strip graphs if there exists a graph G such that G_{0} = G, G_{1} = G +_{R} G, G_{2} = G +_{R} +G +_{R^{−1}} G, G_{3} = G +_{R} G +_{R^{−1}} G +_{R} G, ….

4. Alternating ring graphs if there exists a graph G such that G_{0} = G, G_{1} = G ⊕_{R} G, G_{2} = G ⊕_{R} G ⊕_{R^{−1}} G, G_{3} = G ⊕_{R} G ⊕_{R^{−1}} G ⊕_{R} G, ….

In any case G is called the shape of G and G +_{R} G is called the fundamental pattern of G.

Note that in the ring cases, the fundamental pattern is an open Zykov sum, while the family elements are closed Zykov sums.

In the following theorems, we show that the families given in Definition 9 have Fibonacci series with minor variations of the geometric series.

Theorem 10. Let G be a family of graphs as in Definition 9. Let G be the shape of G, T the transfer matrix of the fundamental pattern and I the identity matrix.

1. If G is a family of strip graphs then

F_{G}(x) = ⟨G|(I − xT)^{−1}|G⟩.  (9)

2. If G a family of ring graphs then

F_{G}(x) = F (G) + Tr (x(I − xT)^{−1}T_{1})  (10)

where T_{1} is the transfer matrix of the skewing of G.

Proof.

1. From Theorem 7, we get, for any n non-negative integer, F (G_{n}) = ⟨G|T^{n}|G⟩. So

F_{G}(x) = ⟨G| ∑_{n=0}^{∞} T^{n}x^{n}|G⟩ = ⟨G|(I − xT)^{−1}|G⟩.

2. Similarly, from Theorem 7, we have F (G_{n}) = Tr (T^{n−1}T_{1}), n ≥ 1. Then

F_{G}(x) = F (G) + ∑_{n=1}^{∞} Tr (T^{n−1}T_{1})x^{n}
= F (G) + Tr (x(I − xT)^{−1}T_{1})

due to the linearity of the matrix trace.

Similarly, we can prove the following.

Theorem 11. Under the notation given in Theorem 10.

1. If G is a family of alternating strip graphs then

F_{G}(x) = ⟨G|(I − x^{2}TT^{t})^{−1}(I + xT)|G⟩.  (11)

2. If G is a family of alternating ring graphs then

F_{G}(x) = Tr ((I − x^{2}TT^{t})^{−1}(I + xT)).

5 Examples

We choose some interesting examples in order to illustrate our methods. We deal with several particular cases of strips, which include cylinders, grids, nanotubes and some kind of cylinders with Petersen graph shape as well as their closed versions as rings: tori, generalized Möbius strips, nanotori, and tori with Petersen graph shape.

Centipedes. Now, our fundamental pattern is P_{2} +_{f} P_{2} given in Figure 1 where the partial function f : {0, 1} → {0, 1} is defined just by f(0) = 0. Next, we take the family of strip

Figure 1: Fundamental pattern of the centipedes

graphs G = (G_{n})_{n≥0} given by open Zykov sums G_{n} = P_{2} +_{f} ⋯ +_{f} P_{2}, where the number of P_{2} is n + 1, n = 0, 1, … Then, the transfer matrix of P_{2} +_{f} P_{2} is

T_{P_{2},P_{2}}^{f} = (\begin{matrix}1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{matrix}) .  (12)

Then, from (9), we get

F_{G}(x) = \frac{3 + 2 x}{1 − 2 x − 2 x^{2}}

which is the generating function, except for the first term, of the sequence \underline{A028859} in [19].

Figure 2: Strip of graphs with fundamental pattern P_{3} +_{R} P_{3}

Diagonal grids. Let P_{3} be the path graph with set of vertices {0, 1, 2}. The family G of strip graphs given in Figure 2 has fundamental pattern P_{3} +_{R} P_{3} where R is the relation on V (P_{3}) defined by 1R 0, 2R 1 (see Figure 3).

Its transfer matrix is

T_{P_{3},P_{3}}^{R} = (\begin{matrix}1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \end{matrix}) .

From (9) it follows that the corresponding Fibonacci series is

F_{G}(x) = −\frac{4 x − 5}{3 x^{2} − 5 x + 1}

which is the generating function of the sequence \underline{A188707}. Similarly, we have that the family of graphs R given in Figure 4 is a family of ring graphs with fundamental pattern and skewing P_{3} +_{R} P_{3}. From (10) we have that its Fibonacci series is

F_{R}(x) = \frac{9 x^{2} − 20 x + 5}{3 x^{2} − 5 x + 1} .

Figure 3: The fundamental pattern P_{3} +_{R} P_{3}

Figure 4: A generic element of the family R

Cylinders. Let C_{i} be the i-cycle graph and P_{n} be the path graph with n vertices. Let Id : V (C_{i}) → V (C_{i}) be the identity map. Then, the cylinder C_{i} × P_{n} is G(i, n) = C_{i} +_{Id} C_{i} +_{Id} ⋯ +_{Id} C_{i}, where the number of cycles is n + 1, n ≥ 0. Thus, the cylinders G(i, ∗) form a family of strip graphs with fundamental pattern C_{i} +_{Id} C_{i} and shape C_{i}. From (9), for some fixed i, we can calculate the generating function F_{G(i,∗)}(x), as shown in Table 2.

i  F_{G(i,∗)}(x)  Sequence
2  −\frac{x+3}{x^{2}+2 x−1}  \underline{A078057}
3  −\frac{x+4}{x^{2}+3x−1}  \underline{A003688}
4  −\frac{x^{2}−7}{x^{3}−x^{2}−5x+1}  \underline{A051926}
5  −\frac{x^{2}−4x−11}{x^{3}−5x^{2}−7x+1}  \underline{A181989}
6  −\frac{x^{4}−x^{3}−25x^{2}−17x+18}{x^{5}−2x^{4}−25x^{3}−3x^{2}+12x−1}  \underline{A181961}
7  −\frac{x^{4}+6x^{3}−38x^{2}−16x+29}{x^{5}+5x^{4}−44x^{3}+8x^{2}+17x−1}  \underline{A182014}
8 −\frac{x^{7}+6x^{6}−105x^{5}+108x^{4}+394x^{3}−163x^{2}−208x+47}{x^{8}+5x^{7}−109x^{6}+187x^{5}+334x^{4}−317x^{3}−65x^{2}+29x−1} \underline{A182019}

Table 2: The Fibonacci series of some cylinders. These are the generating functions of the integer sequences in the third column except for the first term

Tori. Let C_{i} be the cycle graph of length i. Then G(i, n) = C_{i} ⊕_{Id} C_{i} ⊕_{Id} ⋯ ⊕_{Id} C_{i} ⊕_{Id} C_{i} where the number of cycles written is n + 1, n = 0, 1, . . .. Such graph is the torus C_{i} × C_{n}. Thus, the family of ring graphs G(i, ∗) has fundamental pattern and skewing C_{i} +_{Id} C_{i}. Again, we can calculate F_{G(i,∗)} for some particular values of i with the help of (10), as shown in Table 3.

Generalized Petersen graphs. We are dealing with generalized Petersen graphs P (i, 2) defined by V (P (i, 2)) = {0, 1, …, 2i − 1} and

E(P (i, 2)) = {{j, j + i} | 0 ≤ j ≤ i − 1} ∪ {{j, k} | j − k ≡ 0 (mod 2) and i ≤ j, k < 2i} ∪ {{j, k} | k ≡ j + 1 (mod i) and 0 ≤ j, k ≤ i − 1}.

i F_{G(i,∗)}(x)  Sequence
3 \frac{5 x^{2}+7 x−4}{x^{3}+4 x^{2}+2 x−1}  \underline{A051928}
4 −\frac{x^{5}+17 x^{4}−20 x^{3}−72 x^{2}−13 x+7}{x^{6}−2 x^{5}−7 x^{4}+8 x^{3}+15 x^{2}+2 x−1}  \underline{A050402}
5 −\frac{11 x^{6}−27 x^{5}−130 x^{4}+70 x^{3}+220 x^{2}+43 x−11}{x^{7}−8 x^{6}+7 x^{5}+30 x^{4}−10 x^{3}−27 x^{2}−4 x+1} \underline{A182041}
6 −p(x)/q(x)  \underline{A182052}

Table 3: The Fibonacci series of several tori. In the case i = 6 we have p(x) = 9 x^{12}+67 x^{11}− 556 x^{10}−1162 x^{9}+6841 x^{8}−1421 x^{7}−12335 x^{6}+3985 x^{5}+7340 x^{4}−1182 x^{3}−1317 x^{2}−71 x+18 and q(x) = x^{13} − 4 x^{12} − 36 x^{11} + 119 x^{10} + 295 x^{9} − 1032 x^{8} + 115 x^{7} + 1301 x^{6} − 360 x^{5} − 575 x^{4} + 89 x^{3} + 84 x^{2} + 4 x − 1

The Fibonacci number for generalized Petersen graphs P (i, 2) with i an odd number was calculated by Wagner [20]. Here we calculate the Fibonacci series for the family of generalized Petersen graphs using the transfer matrix method. Let P_{4} be the the path graph with vertices V (P_{4}) = {0, 1, 2, 3}. Let R be the relation on V (P_{4}) defined by 0R 0, 3R 3, 2R 1 (see Figure 5).

Figure 5: Fundamental pattern in the Petersen graphs P (2i, 2)

Then, the ring graph family with shape P_{4}, fundamental pattern P_{4} +_{R} P_{4} and skewing the same P_{4} +_{R} P_{4}, is the family of generalized Petersen graphs G = (P (2i, 2))_{i≥0}:

P (2i, 2) = P_{4} ⊕_{R} P_{4} ⊕_{R} ⋯ ⊕_{R} P_{4} ⊕_{R} P_{4},

where P_{4} appears i+1 times, i = 0, 1, . . .. Note that we included the non-standard generalized Petersen graphs P (0, 2) = P_{4} and the multigraph P (2, 2) = P_{4} ⊕_{R} P_{4}.

The related transfer matrix is

T_{P_{4},P_{4}}^{R} = (\begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \end{matrix}) .  (13)

Then, from (10), we get

F_{G}(x) = \frac{(6 x^{2} − 11 x − 8) (2 x^{3} − 5 x^{2} − 4 x + 1)}{4 x^{5} − 13 x^{4} + 3 x^{3} + 15 x^{2} + 3 x − 1}

which is the generating function of \underline{A182054}.

For generalized Petersen graphs of the type P (2i+1, 2), i ≥ 2 we take the family P given in Figure 7, i.e.,

P (2i + 1, 2) = ⨁_{R_{1}}_{k=1}^{i−1}P_{4} ⊕_{R_{2}} M ⊕_{R_{3}} P_{4}

where M is the graph such that V (M) = {0, 1, 2, 3, 4, 5}, E(M) = {{0, 1}, {1, 2}, {2, 3}, {2, 4}, {4, 5}, {0, 5}} and relations R_{1} = {(0, 0), (3, 3), (2, 1)}, R_{2} = {(0, 0), (3, 3), (2, 1)}, R_{3} = {(3, 0), (5, 3), (4, 1)}.

From the Theorem 7 and proof of (10) in Theorem 10, we get

F_{P}(x) = ∑_{j=0}^{∞} Tr(T_{1}^{j}T_{2}T_{3})x^{j} = Tr ((I − xT_{1})^{−1}T_{2}T_{3})

where T_{1} = T_{P_{4},P_{4}}^{R_{1}} is given by (13); while T_{2} = T_{P_{4},M}^{R_{2}} and T_{3} = T_{M,P_{4}}^{R_{3}} are 8 × 19 and 19 × 8 matrices respectively. Thus,

F_{P}(x) = −\frac{52 x^{4} − 165 x^{3} + 16 x^{2} + 207 x + 76}{4 x^{5} − 13 x^{4} + 3 x^{3} + 15 x^{2} + 3 x − 1}

which is the generating function of \underline{A182077} with a shift of one term.

Families with Petersen graph shape. Let Id : V (P (5, 2)) → V (P (5, 2)) be the identity map. We take G as the family of strip graphs with fundamental pattern P (5, 2) +_{Id} P (5, 2) and shape of the Petersen graph P (5, 2), i.e., G = (G_{n})_{n≥0} where G_{n} = P (5, 2)+_{Id} P (5, 2)+_{Id} ⋯ +_{Id} P (5, 2) with n + 1 copies of the Petersen graph, n ≥ 0 (see Figure 8). Then, the transfer matrix T_{P (5,2),P (5,2)}^{Id} is a 76 × 76-matrix, since F (P (5, 2)) = 76.

Figure 6: Generalized Petersen graph P (2i, 2).

Figure 7: The family of graphs P (2i + 1, 2)

From (9) we get

F_{G}(x) = −\frac{x^{5} + 12 x^{4} − 130 x^{3} + 92 x^{2} + 237 x + 76}{x^{6} + 11 x^{5} − 137 x^{4} + 172 x^{3} + 215 x^{2} + 39 x − 1}.

Similarly, for G′ the family of ring graphs with fundamental pattern and skewing given by P (5, 2) +_{Id} P (5, 2), we get from (10), that its Fibonacci series F_{G′}(x) satisfies F_{G′}(x) = p(x)/q(x) where

p(x) = 59 x^{20} + 158 x^{19} − 17410 x^{18} − 31425 x^{17} + 843564 x^{16} + 1040034 x^{15}

− 10876134 x^{14} − 9246646 x^{13} + 52315426 x^{12} + 29197770 x^{11} − 101636518 x^{10} − 28773932 x^{9} + 77606056 x^{8} + 9105678 x^{7} − 21502410 x^{6} − 847682 x^{5} + 1979331 x^{4}

+ 80616 x^{3} − 50408 x^{2} − 2203 x + 76

and

q(x) = (x − 1) (x^{2} + 2 x − 1) (x^{5} + 5 x^{4} − 4 x^{3} − 14 x^{2} + 3 x + 1)

(x^{6} + 11 x^{5} − 137 x^{4} + 172 x^{3} + 215 x^{2} + 39 x − 1) (x^{7} + 4 x^{6} − 52 x^{5} − 105 x^{4} + 51 x^{3} + 78 x^{2} − 10 x − 1) .

We obtain an additional family G′′ if, instead of closing with the relation given by the identity map, we take a rotation R by an angle of 2π/5. More formally, we take V (P (5, 2)) =

Figure 8: A strip graph with shape P (5, 2), the Petersen graph. The edges given by the identity map are shown by dotted lines Figure 9: A pair of rings with shape P (5, 2), the Petersen graph. The edges given by the relation maps are shown by dotted lines. The ring on the left has relation maps the identity map; while the ring on the right has skewing given by the relation R = {(0, 1) , (1, 2) , (2, 3) , (3, 4) , (4, 0) , (5, 6) , (6, 7) , (7, 8) , (8, 9) , (9, 5)}. The former ring has Fibonacci number 27,053,615,385,404,201. The latter has Fibonacci number 27,050,814,022,108,001.

{0, 1, 2, …, 9} as the vertices set of the Petersen graph, and

E(P (5, 2)) = {{0, 1} , {0, 4} , {0, 5} , {1, 2} , {1, 6} , {2, 3} , {2, 7} , {3, 4} , {3, 8} , {4, 9} , {5, 7} , {5, 8} , {6, 8} , {6, 9} , {7, 9}} .

Then, the new skewing induced by R is defined as follows (see Figure 9)

R = {(0, 1) , (1, 2) , (2, 3) , (3, 4) , (4, 0) , (5, 6) , (6, 7) , (7, 8) , (8, 9) , (9, 5)} .

Then F_{G′′}(x) = p_{1}(x)/q_{1}(x), where

p_{1}(x) = 75 x^{15} + 1284 x^{14} − 8828 x^{13} − 101662 x^{12} + 376556 x^{11} + 1642004 x^{10}

− 2174799 x^{9} − 7893320 x^{8} + 252699 x^{7} + 6559072 x^{6} + 1031350 x^{5} − 1259454 x^{4}

− 160398 x^{3} + 47456 x^{2} + 2305 x − 76

and

q_{1}(x) = (x^{2} + 2 x − 1) (x^{6} + 11 x^{5} − 137 x^{4} + 172 x^{3} + 215 x^{2} + 39 x − 1) (x^{7} + 4 x^{6} − 52 x^{5} − 105 x^{4} + 51 x^{3} + 78 x^{2} − 10 x − 1) .

Armchair nanotube graphs. Let B_{n} be the graph with 2n vertices {0, 1, …, 2n − 1} and set of edges {{0, 1}, {2, 3}, …, {2n−2, 2n−1}}, i.e., B_{n} is the disjoint union of n copies of the one-length path P_{2}:

B_{n} = P_{2} +_{∅} ⋯ +_{∅} P_{2}.

We define a relation map R : V (B_{n}) → V (B_{n}) as R(i) = (i − 1) mod 2n, i = 0, …, 2n − 1. An armchair nanotube graph of length n and breadth k is

NT_{n,k} = B_{n} +_{R} B_{n} +_{R^{−1}} B_{n} +_{R} ⋯ +_{R^{±1}} B_{n}

where B_{n} appears k + 1 times, k ≥ 0 (this graph forms the structure of the (n, n) armchair carbon nanotube [14] without caps). Thomassen [16] defines a similar graph called hexagonal cylinder circuit, however this belongs to a different family of nanotubes: zig-zag carbon nanotubes.

By definition NT_{n,∗} = (NT_{n,k})_{k≥0} is a family of alternating strip graphs with fundamental pattern B_{n} +_{R} B_{n}. By (11) and a calculation similar to those in the previous examples, we get that the Fibonacci series of the armchair nanotube graphs of length 3 is

F_{NT_{3,∗}}(x) = −\frac{28 x^{4} + 55 x^{3} − 89 x^{2} − 29 x + 27}{28 x^{5} + 42 x^{4} − 109 x^{3} + 17 x^{2} + 13 x − 1}

which is the generating function of \underline{A182130}.

Similarly, a nanotorus graph is the following closed Zykov sum:

Nτ_{n,k} = B_{n} ⊕_{R} B_{n} ⊕_{R^{−1}} B_{n} +_{R} ⋯ ⊕_{R^{±1}} B_{n},

where, again, B_{n} appears k + 1 times, k ≥ 0. Now the family Nτ_{3,∗} = (Nτ_{3,k})_{k≥0} has Fibonacci series F_{Nτ_{3,∗}}(x) = p(x)/q(x), where

p(x) = 979776 x^{18} − 75600 x^{17} − 12197940 x^{16} + 5916552 x^{15} + 35833019 x^{14} − 19220271 x^{13} − 44070216 x^{12} + 23310438 x^{11} + 26177559 x^{10} − 13274349 x^{9}

− 7520073 x^{8} + 3654387 x^{7} + 940365 x^{6} − 451464 x^{5} − 43362 x^{4} + 24495 x^{3}
+ 25 x^{2} − 468 x + 27

and

q(x) = (x − 1) (x + 1) (3 x^{3} − 5 x^{2} − 5 x + 1) (36 x^{4} − x^{3} − 20 x^{2} − x + 1) (36 x^{4} + x^{3} − 20 x^{2} + x + 1) (28 x^{5} + 42 x^{4} − 109 x^{3} + 17 x^{2} + 13 x − 1) .

The rational function F_{Nτ_{3,∗}}(x) is the generating function of the sequence \underline{A182141}.

Generalized Möbius Ladders. Let P_{n} be the path graph with n vertices, V (P_{n}) = {0, …, n − 1}, σ be a permutation of V (P_{n}) and Id be the identity map on V (P_{n}). Then a generalized Möbius ladder M(n, m, σ) is

M(n, m, σ) = P_{n} ⊕_{Id} ⋯ ⊕_{Id} P_{n} ⊕_{σ} P_{n}

where P_{n} appears m + 1 times, m = 0, 1, …; for instance, if σ : V (P_{2}) → V (P_{2}) is the transposition σ(0) = 1 and σ(1) = 0 then M(2, ∗, σ) = (M(2, m, σ))_{m≥0} is the family of usual Möbius ladders. The family of ring graphs M(2, ∗, σ) has fundamental pattern P_{2} +_{Id} P_{2} and skewing P_{2} +_{σ} P_{2}. We have the transfer matrices,

T_{P_{2},P_{2}}^{Id} = (\begin{matrix}1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix}) , T_{P_{2},P_{2}}^{σ} = (\begin{matrix}1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix}) .

Figure 10: The nanotube graph NT_{5,21} on the left and the nanotorus graph Nτ_{5,21} on the right. Once again, the edges given by the relation set are shown by dotted lines. Using Theorem 7 we get that the nanotube graph NT_{5,21} has Fibonacci number 14,890,453,762,710,452,477,470,450,680,772,895,445,343; while the nanotorus graph Nτ_{5,21} has Fibonacci number 73,562,247,493,061,556,896,479,759,292,362,159,745

Then, from (10), we get

F_{M(2,∗,σ)}(x) = \frac{2 x^{3} + 7 x^{2} − 3}{(x + 1) (x^{2} + 2 x − 1)}

which is the generating function of \underline{A182143} except for the first term.

Now, we take families M(3, ∗, σ_{i}) = (M(3, m, σ_{i}))_{m≥0}, i = 1, 2, 3 with σ_{1}, σ_{2}, σ_{3} permutations of V (P_{3}) defined in Figure 11. Thomassen [16] calls the family of graphs M(3, σ_{2}) quadrilateral Möbius double circuits.

We have

T_{P_{3},P_{3}}^{σ_{1}} = (\begin{matrix}1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{matrix}) , T_{P_{3},P_{3}}^{σ_{2}} = (\begin{matrix}1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \end{matrix}) ,

T_{P_{3},P_{3}}^{σ_{3}} = (\begin{matrix}1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 \end{matrix}) , T_{P_{3},P_{3}}^{Id} = (\begin{matrix}1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \end{matrix}) .

Then

F_{M(3,∗,σ_{1})}(x) = \frac{3 x^{5} + 6 x^{4} − 19 x^{3} − 30 x^{2} − 2 x + 5}{(x + 1) (x^{4} − 6 x^{2} − 2 x + 1)},

F_{M(3,∗,σ_{2})}(x) = \frac{2 x^{5} + x^{4} − 24 x^{3} − 28 x^{2} − 2 x + 5}{(x + 1) (x^{4} − 6 x^{2} − 2 x + 1)},

and

F_{M(3,∗,σ_{3})}(x) = \frac{4 x^{5} + 6 x^{4} − 25 x^{3} − 32 x^{2} − x + 5}{(x + 1) (x^{4} − 6 x^{2} − 2 x + 1)}.

Figure 11: A subset of permutations of V (P_{3})

Some regular and almost regular graphs. Let B_{n} be the disjoint union of n copies of the singleton graph K_{1}, i.e, V (B_{n}) = {0, …, n − 1} and E(B_{n}) = ∅. Let R be the relation on V (B_{n}) given by iRi and iRj where j ≡ i − 1 (mod n), i = 0, … n − 1. Note that R is also a relation from vertices of the n-cycle C_{n} to those of B_{n}. We define

G_{n}^{k} = C_{n} +_{R} B_{n} +_{R} ⋯ +_{R} B_{n}
R_{n}^{k+1} = C_{n} +_{R} B_{n} +_{R} ⋯ +_{R} B_{n} +_{R} C_{n}

where B_{n} appears k − 1 times, k = 1, 2, … and G_{n}^{0} = R_{n}^{0} = ∅ the empty graph, R_{n}^{1} = C_{n}. Furthermore, let C′_{n} be the complement graph of the n-cycle graph C_{n} and K_{n} the complete graph on n vertices with V (K_{n}) = {0, 1, …, n − 1}. Also, we define

K_{n}^{k} = C′_{n} +_{R} ⋯ +_{R} C′_{n} +_{R} K_{n}
P_{n}^{k+1} = K_{n} +_{R} C′_{n} +_{R} ⋯ +_{R} C′_{n} +_{R} K_{n}

where C′_{n} appears k − 1 times, k = 1, 2, … and K_{n}^{0} = P_{n}^{0} = ∅, P_{n}^{1} = K_{n}. The graphs G_{n}^{k}, R_{n}^{k}, K_{n}^{k} and P_{n}^{k} are called (almost) regular graphs class 1, class 2, class 3 and class 4, respectively by Burstein, Kitaev, and Mansour [1]. Thus, from Theorem 7, we get

F_{G_{n}^{∗}}(x) = 1 + F (C_{n}) x + ⟨C_{n}|T_{C_{n},B_{n}}^{R}(I − x T_{B_{n},B_{n}}^{R})^{−1}|B_{n}⟩ x^{2},  (14)

F_{R_{n}^{∗}}(x) = 1 + F (C_{n}) x + ⟨C_{n}| (x^{2} T_{C_{n},C_{n}}^{R} + x^{3} T_{C_{n},B_{n}}^{R}(I − x T_{B_{n},B_{n}}^{R})^{−1}T_{B_{n},C_{n}}^{R}) |C_{n}⟩, (15)
F_{K_{n}^{∗}}(x) = 1 + (n + 1) x + ⟨C′_{n}|(I − x T_{C′_{n},C′_{n}}^{R})^{−1}T_{C′_{n},K_{n}}^{R}|K_{n}⟩ x^{2},  (16)
F_{P_{n}^{∗}}(x) = 1 + (n + 1) x + ⟨K_{n}| (x^{2} T_{K_{n},K_{n}}^{R} + x^{3} T_{K_{n},C′_{n}}^{R}(I − x T_{C′_{n},C′_{n}}^{R})^{−1}T_{C′_{n},K_{n}}^{R}) |K_{n}⟩. (17)

Burstein et al [1] introduce algorithms for computing the Fibonacci series of the families G_{n}^{∗}, R_{n}^{∗}, K_{n}^{∗}, and P_{n}^{∗}. However these algorithms fail for the families R_{n}^{∗}, K_{n}^{∗} and P_{n}^{∗}. For instance, it is easy to see that F (R_{3}^{3}) = 32, while 32 does not appear in the sequence \underline{A026150} which is the Fibonacci numbers sequence of the family R_{3}^{∗}, according to Burstein et al. Also F (K_{4}^{2}) = 25, F (P_{4}^{3}) = 77 are counterexamples to Theorem 3.3 and Theorem 3.4 of [1], respectively. As a consequence, since 77 does not appear in \underline{A007483}, Burstein et al

n F_{R_{n}^{∗}}(x)  F_{K_{n}^{∗}}(x)  Sequence
3 −\frac{4 x^{2}−1}{2 x^{2}−4 x+1}  \frac{1}{2 x^{2}−4 x+1}  \underline{A007070}
4 \frac{10 x^{5}+41 x^{4}−38 x^{3}−14 x^{2}+4 x+1}{7 x^{4}+15 x^{3}−14 x^{2}−3 x+1}  \frac{3 x^{2}+2 x+1}{x^{3}−7 x^{2}−3 x+1}
5 \frac{55 x^{6}−193 x^{5}−303 x^{4}+149 x^{3}+39 x^{2}−6 x−1}{22 x^{5}−31 x^{4}−69 x^{3}+30 x^{2}+5 x−1}  \frac{4 x^{2}+x+1}{x^{3}−7 x^{2}−5 x+1}
6 \frac{516 x^{8}−248 x^{7}−3688 x^{6}+1834 x^{5}+2518 x^{4}−588 x^{3}−112 x^{2}+10 x+1}{108 x^{7}−84 x^{6}−532 x^{5}+178 x^{4}+280 x^{3}−66 x^{2}−8 x+1} \frac{5 x^{2}+1}{x^{3}−7 x^{2}−7 x+1}

Table 4: Some Fibonacci series of classes 2 and 3 graphs

[1] are wrongfully relating this sequence to the class 4 graphs. The correct Fibonacci series, after the formulas (15), (16) and (17) are shown in Tables 4 and 5.

Due to Theorem 10, the family ∅, C_{3}, C_{3} +_{R} C_{3}, C_{3} +_{R} C_{3} +_{R} C_{3}, … has Fibonacci series (2 x + 1)/(2 x^{2} + 2 x − 1) which is the generating function of \underline{A026150}; while the family ∅, K_{4}, K_{4} +_{R} K_{4}, K_{4} +_{R} K_{4} +_{R} K_{4}, … has Fibonacci series −(2 x + 1)/(2 x^{2} + 3 x − 1) which is the generating function of \underline{A007483}.

n F_{P_{n}^{∗}}(x)  Sequence
3 −\frac{(2 x−1) (2 x+1)}{2 x^{2}−4 x+1}  \underline{A161941}
4 −\frac{8 x^{3}+5 x^{2}−2 x−1}{x^{3}−7 x^{2}−3 x+1}
5 −\frac{10 x^{3}+11 x^{2}−x−1}{x^{3}−7 x^{2}−5 x+1}
6 −\frac{12 x^{3}+19 x^{2}−1}{x^{3}−7 x^{2}−7 x+1}

Table 5: Some Fibonacci series of the class 4 graphs. The series F_{P_{3}^{∗}}(x) is the generating function of two times the terms in \underline{A161941} except the first one

6 Acknowledgements

The authors would like to thank Luke Goodman for helpful comments and suggestions.

References

[1] A. Burstein, S. Kitaev, and T. Mansour, Counting independent sets in some classes of (almost) regular graphs, Pure Math. Appl. (PU.M.A.) 19 (2008), 17–26.

[2] N. Calkin and H. S. Wilf, The number of independent sets in a grid graph, SIAM J. Discrete Math. 11 (1997), 54–60.

[3] T. Carroll, D. Galvin, and P. Tetali, Matchings and independent sets of a fixed size in regular graphs, J. Combin. Theory Ser. A 116 (2009), 1219–1227.

[4] J. Cutler and A. J. Radcliffe, Extremal graphs for homomorphisms, J. Graph Theory 67 (2011), 261–284.

[5] R. Diestel, Graph Theory, Springer, 2006.

[6] K. Engel, On the Fibonacci number of an m × n lattice, Fibonacci Quart. 28 (1990), 72–78.

[7] R. Euler, The Fibonacci number of a grid graph and a new class of integer sequences, J. Integer Seq. 8 (2005), Article 05.2.6.

[8] D. Galvin, Two problems on independent sets in graphs, Discrete Math. 311 (2011), 2105–2112.

[9] D. Galvin and Y. Zhao, The number of independent sets in a graph with small maximum degree, Graphs Combin. 27, (2011) 177–186.

[10] M. Golin, Y. C. Leung, Y. J. Wang, and X. R. Yong, Counting structures in grid-graphs, cylinders and tori using transfer matrices: Survey and new results, in C. Demetrescu, R. Sedgewick, and R. Tamassia, eds., Proceedings of the Second Workshop on Analytic Algorithmics and Combinatorics (ANALCO05), SIAM, 2005, pp. 250–258.

[11] A. Knopfmacher, R. F. Tichy, S. Wagner, and V. Ziegler, Graphs, partitions and Fibonacci numbers, Discrete Appl. Math. 155 (2007), 1175–1187.

[12] R. E. Merrifield and H. E. Simmons, Topological Methods in Chemistry, Wiley, 1989.

[13] A. S. Pedersen and P. D. Vestergaard, The number of independent sets in unicyclic graphs, Discrete Appl. Math. 152 (2005), 246–256.

[14] C. P. Poole, Jr. and F. J. Owens, Introduction to nanotechnology, Wiley, 2003.

[15] H. Prodinger and R. F. Tichy, Fibonacci numbers of graphs, Fibonacci Quart. 20 (1982), 16–21.

[16] C. Thomassen, Tilings of the torus and the Klein bottle and vertex-transitive graphs on a fixed surface, Trans. Amer. Math. Soc. 323 (1991), 605–635.

[17] A. A. Sapozhenko, The number of independent sets in graphs, Moscow Univ. Math. Bull. 62 (2007), 116–118.

[18] I. Stojmenovic, Honeycomb networks: Topological properties and communication algorithms, IEEE Trans. Parallel Distrib. Syst. 8 (1997), 1036–1042.

[19] The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[20] S. G. Wagner, The Fibonacci number of generalized Petersen graphs, Fibonacci Quart. 44 (2006), 362–367.

[21] Y. Zhao, The number of independent sets in a regular graph, Combin. Probab. Comput. 19 (2010), 315–319.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 05C76, 11B83, 05A15, 05C69. Keywords: Fibonacci number, Merrifield-Simmons index, independent set, Zykov sum, transfer matrix method.

(Concerned with sequences \underline{A003688} \underline{A007070} \underline{A007483} \underline{A026150} \underline{A028859} \underline{A050402} \underline{A051926}

\underline{A051928} \underline{A078057} \underline{A161941} \underline{A181961} \underline{A181989} \underline{A182014} \underline{A182019} \underline{A182041} \underline{A182052} \underline{A182054}

\underline{A182077} \underline{A182130} \underline{A182141} \underline{A182143} and \underline{A188707}.)

Received May 4 2012; revised August 22 2012; September 13 2012. Published in Journal of Integer Sequences, September 23 2012.

Return to Journal of Integer Sequences home page.