<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}
\hyphenation{Se-quen-ces na-no-tu-be U-sing Fi-bo-na-cci}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\DeclareMathOperator{\Id}{Id}
\DeclareMathOperator{\Tr}{Tr}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}


\begin{center}
\vskip 1cm{\LARGE\bf 
Fibonacci Numbers 
of \\  \vskip .12in
Generalized Zykov Sums
}
\vskip 1cm
\large
C\'esar Bautista-Ramos and Carlos Guill\'en-Galv\'an \\
Facultad de Ciencias de la Computaci\'on\\
Benem\'erita Universidad Aut\'onoma de Puebla\\
14 Sur y Av. San Claudio, Edif. 104C, 303 \\
Puebla, Pue. 72570\\
Mexico\\
\href{mailto:bautista@cs.buap.mx}{\tt bautista@cs.buap.mx} \\
\href{mailto:cguillen@cs.buap.mx}{\tt cguillen@cs.buap.mx}\\
\end{center}

\vskip .2 in


\newcommand{\C}{\mathcal{C}}
\newcommand{\G}{\mathcal{G}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}


\newcommand{\braket}[2]{\langle #1|#2\rangle}
\newcommand{\ocup}{\stackrel{\cdot}{\cup}}
\newcommand{\bra}[1]{\langle#1 |}
\newcommand{\ket}[1]{|#1\rangle }
\newcommand{\vect}[1]{\boldsymbol{#1}}

\begin{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\"obius ladders, carbon nanotube graphs, among others).
\end{abstract}

\section{Introduction}
\label{intro}
The Fibonacci number $F(G)$ of a graph $G$  was introduced by
Prodinger and Tichy
\cite{Prodinger}  and  is defined
as the number of independent sets of $G$. In combinatorial chemistry
this number is also known as the Merrifield-Simmons index \cite{Knop, Merrifield}. Prodinger and Tichy 
calculated $F(G)$  recursively by paying attention to whether certain
vertices appear or not
in what they  call  {\it the usual recursion argument}.  Such
binary occurrence problem is formalized, in this paper,  in the {\it
  transfer matrix method} \cite{Calkin,Engel,Euler,Golin}. 

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 {\it 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 \ref{thm:sum}). Such binary
information, whether vertices are related or not, is
stored in a matrix known as the {\it transfer matrix} \cite{Calkin,Engel,Euler,Golin}. 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\"obius 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 \cite{Stoj} and
nanotechnology \cite{nano}.
 

There are other works dealing with the Fibonacci number $F(G)$ when
$G$ has a different structure from those studied here; for
instance, trees \cite{Knop}, 
 regular graphs \cite{Carroll, Sapozhenko,Zhao},
 unicyclic graphs  \cite{Pedersen}, graphs with small maximum degree
\cite{Galvin2}, graphs with a given number of vertices and edges \cite{Cutler},
and graphs with a given minimum degree \cite{Galvin}. 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
\cite{Golin},  Euler \cite{Euler}, Prodinger and
Tichy \cite{Prodinger},  Warner \cite{Wagner},  Engel \cite{Engel}, Calkin and Wilf  \cite{Calkin}, Burnstein, Kitaev, and
 Mansour \cite{Burstein}, among others. However, there are some
errors in \cite{Burstein}, as we show in Section  \ref{sec:examples}.

This paper is organized as follows: In Section  \ref{sec:definitions}
we introduce the basic definitions and
some examples; in Section  \ref{sec:counting} we give  the related
theorems for counting independent sets along  with some  examples; in Section   \ref{sec:series}, we calculate the generating function of the Fibonacci numbers for some
families of open and closed Zykov sums. Finally, in Section
\ref{sec:examples}, we describe more
examples, among them (almost) regular graphs \cite{Burstein}
where we  also show some counterexamples to the calculations in \cite{Burstein}. 


\section{Definitions}\label{sec:definitions}

 In this paper we  deal only with  multigraphs
 \cite{Diestel}. 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$,
 $\oplus_R$ respectively.  Both are defined below.
\begin{definition}\label{sumaZykov} Let  $\uplus$ be the disjoint union operator.
  Let $G_1,\ldots,G_n$ be a collection of graphs  and
  $R_1,\ldots,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,\ldots,n-1$ . Let $E_i=\{\{v,w\}\subseteq
  V(G_i)\uplus V(G_{i+1})\,|\,v\in V(G_i), w\in
  V(G_{i+1})\text{ with }vR_iw\}$, $i=1,\ldots,n-1$.
  We
  define a new graph $G_1+_{R_1}\cdots+_{R_{n-1}} G_n$ as follows: 
\[
V(G_1+_{R_{1}}\cdots+_{R_{n-1}} G_n)=V(G_1)\uplus \cdots\uplus V(G_n)
\]
and
\[
E(G_1+_{R_1}\cdots+_{R_{n-1}} G_n)=E(G_1)\uplus\cdots\uplus
E(G_n)\uplus E_1\uplus\cdots\uplus E_{n-1}.
\] 
  We call  $G_1+_{R_1}\cdots+_{R_{n-1}} G_n$ 
an  {\it 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\oplus_{R_1}\cdots\oplus_{R_{n-1}} G_n\oplus_{R_{n}} G_1$ as
\[
V(G_1\oplus_{R_1}\cdots\oplus_{R_{n-1}} G_n\oplus_{R_{n}}G_1)=V(G_1)\uplus \cdots\uplus V(G_n)
\]
and
\[
E(G_1\oplus_{R_1}\cdots\oplus_{R_{n-1}} G_n\oplus_{R_{n}}
G_1)=E(G_1)\uplus\cdots\uplus E(G_n)\uplus E_1\uplus\cdots\uplus E_n
\]
where $E_n=\{\{u,v\}\,:\, u\in V(G_n)\text{ and }v\in
V(G_1)\text{ with } uR_{n}v\}$. We call  $G_1\oplus_{R_1}\cdots\oplus_{R_{n-1}} G_n\oplus_{R_{n}} G_1$ a  {\it closed Zykov sum}\,.
\end{definition}


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

\subsection{Examples} Let $C_n$ be the $n$-cycle graph
with $V(C_n)=\{0,1,\ldots,n-1\}$ and
$E(C_n)=\{\{0,1\},\ldots,\{n-2,n-1\},\{n-1,0\}\}$, where $n=1,2,\ldots$ 

  \paragraph{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 \ref{tab:platonic}. 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^{\pm 1}$  nor $R_2^{\pm 1}$ is a function. 



\begin{table}[th]
  \begin{center}
\begin{tabular}{lll}
\hline\noalign{\smallskip}
 Graph name &amp; Zykov sum &amp; Relation \\
\noalign{\smallskip}\hline\noalign{\smallskip}
Tetrahedral &amp; $C_1+ _R C_3$ &amp; $R=\{(0,0),(0,1),(0,2)\}$\\
Octahedral &amp; $C_3+_R C_3$ &amp;
$R=\{(0,0),(0,2),(1,1),(1,0),$ \\
&amp; &amp; $(2,2),(2,1)\}$\\
Cube &amp;$C_4+_{\Id} C_4$ &amp; $\Id$ identity map on $V(C_4)$\\
Icosahedral &amp; $C_3+_{R_1}C_6+_{R_2} C_3$ &amp;
$R_1=\{(0,0),(0,1),(0,2),(1,2),$\\
 &amp; &amp; $(1,3), (1,4),(2,4),(2,5),(2,0)\}$\\
 &amp;&amp; $R_2=\{(0,0),(1,0),(1,1),(2,1),$\\
 &amp;&amp;  $(3,1), (3,2),(4,2),(5,2),(5,0)\}$\\
Dodecahedral &amp; $C_5+_{R_1}C_{10}+_{R_2^{-1}} C_5$ &amp;
$R_1,R_2:V(C_5)\rightarrow V(C_{10})$\\
&amp; &amp; $R_1(i)=2i,R_2(i)=2i+1$\\
\noalign{\smallskip}\hline
\end{tabular}
\end{center}
\caption{The platonic graphs as open Zykov sums. The graphs $C_n$ are the $n$-cycle
    graphs}
  \label{tab:platonic}     
\end{table}



  \paragraph{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\geq
  0$ where $\Id_n$ is the identity map on $V(Q_n)$.


\paragraph{Paths.} Let $P_0$ be the singleton graph, where
$V(P_0)=\{v_0\}$ and $E(P_0)=\varnothing$.  Let
$\Id:\{v_0\}\rightarrow\{v_0\}$ be the identity
map. Then\[
P_{n}=P_0+_{\Id} P_0+_{\Id}\cdots+_{\Id} P_0
\] 
is the path graph of length $n-1$, where $P_0$ appears $n$ times.

 \paragraph{Grids, cylinders and tori.}
The grid $G_{n,m}$ is defined by $V(G_{n,m})=\{(i,j)\,:\,1\leq  i\leq n, 1\leq j\leq m\}$ and $E(G_{n,m})=\{\{(i,j),(u,v)\}\,:\,|i-u|+|j-v|=1\}$. Then 
\begin{equation}
  \label{eq:1}
G_{n,m}= P_n+_{\Id} P_n+_{\Id}\cdots+_{\Id} P_n
\end{equation}
 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\times m$, as an open Zykov sum, is
\[
C_{n,m}=C_n+_{\Id}C_n+_{\Id}\cdots+_{\Id} C_n
\]
where $C_n$ appears $m$ times. On the other hand, the closed Zykov sum
\[
T_{n,m}=C_n\oplus_{\Id}C_n\oplus_{\Id}\cdots\oplus_{\Id} C_n
\]
is the torus $n\times 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 \ref{sumaZykov}).




\section{Counting independent sets} \label{sec:counting}
 In order to  count independent sets, we are using the transfer
 matrix method \cite{Calkin,Engel,Euler,Golin}, 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.

\begin{definition}
Let $B=\{0,1\}$ and let $G,H$ be a pair of graphs. Let $B^{V(G)}$ be
  the cartesian product $\prod_{v\in 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 $\vect{a}\in B^{V(G)},\vect{b}\in B^{V(H)}$ we define 
\[
\braket{\vect{a}}{\vect{b}}_{R}=\sum_{\substack{v,w\\vRw}}\pi_{v}(\vect{a})\pi_{w}(\vect{b})\in\N
\]
where $\pi_v:B^{V(G)}\rightarrow B_v=B$, $\pi_w:B^{V(H)}\rightarrow B_w=B$
are the canonical projections.
\end{definition}


Let $2^{V(G)}$ be the power set of $V(G)$. There exists a unique
bijection $\vect{\Psi}_{G}:2^{V(G)}\rightarrow B^{V(G)}$
such that 
\begin{equation}
  \label{eq:2}
  \pi_{v}\vect{\Psi}_{G}(A)=\chi_A(v),\quad\forall v\in V(G),\,\forall
  A\subset V(G) 
\end{equation}
where $\chi_A$ is the characteristic function of the set $A$.

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

 
\begin{lemma}\label{uno}
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\uplus B$ is an independent set of $G+_R H$ if
and only if $\braket{\vect{\Psi}_{G}(A)}{\vect{\Psi}_{H}(B)}_{R}=0$.
\end{lemma}
\begin{proof}  The disjoint union
$A\uplus B$ is an
independent set of $G+_R H$ iff for any $v\in V(G), w\in V(H)$, $vRw$ implies $ \{v,w\}\not\subset
A\uplus B$ iff  $vRw$ implies $\chi_{A}(v)\chi_{B}(w)=0$ iff
\[\sum_{\substack{v,w\\vRw}}\pi_{v}(\vect{\Psi}_{G}(A))
\pi_{w}(\vect{\Psi}_{H}(B))=0
\]
because of \eqref{eq:2}.
\end{proof}

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

\begin{definition}
  \begin{enumerate}
  \item For a graph $G$, we denote the
    collection of independent sets of $G$ with $\mathcal{I}_G$; while $F(G)$, called the
    {\it Fibonacci number of $G$},  stands for
    the cardinality  of $\mathcal{I}_G$, i.e., $F(G)=|\mathcal{I}_G|$.
\item For any $z\in \N$ we define 
\[
\overline{z}=
\begin{cases}
  1, &amp;\text{ if }z=0;\\
  0, &amp;\text{ otherwise.}
\end{cases}
\]
\item  Let $G,H$ be a pair of graphs  and  $R$ be a relation from
  $V(G)$ to $V(H)$. The function 
\[{\bf T}_{G,H}^R:\mathcal{I}_G\times
\mathcal{I}_H\rightarrow B,\quad {\bf
  T}_{G,H}^R(A,B)=\overline{\braket{\vect{\Psi}_{G}(A)}{\vect{\Psi}_{H}(B)}_{R}}
\]
is called {\it the transfer matrix} of $G+_R H$.
  \end{enumerate}
\end{definition}

Note that for any $z_1,z_2\in \N$,
$\overline{z_1+z_2}=\overline{z_1}\,\overline{z_2}$. In the following
Theorems \ref{thm:sum} and \ref{thm:dos}, we show how
to calculate the Fibonacci number of open and closed Zykov sums.

\begin{theorem}\label{thm:sum}
  Let $G,H$ be a pair of graphs and  $R$ be a
  relation from $V(G)$ to  $V(H)$. Then
  \begin{enumerate}
  \item \[
F(G+_R H)=\sum_{A\in \mathcal{I}_G,B\in\mathcal{I}_H}{\bf T}_{G,H}^R(A,B)
\]
where ${\bf T}_{G,H}^R$ is the transfer matrix of $G+_R H$.
\item If $G=H$,
\[
F(G\oplus_R G)=\sum_{A\in\mathcal{I}_G} {\bf T}_{G,G}^R(A,A)
\]
where ${\bf T}_{G,G}^R$ is the transfer matrix of $G+_R G$.
  \end{enumerate}
\end{theorem}

\begin{proof}
\begin{enumerate}
\item 
  We have that if  $J\in \I_{G+_R{H}}$ then  there exist $A\in \I_G$ and
  $B\in \I_H$ such that $J=A\uplus B$. Now, use Lemma \ref{uno}.
\item We have that $J\in \mathcal{I}_{G\oplus_R G}$ iff $J\in
  \mathcal{I}_G$ and $\braket{\vect{\Psi}(J)}{\vect{\Psi}(J)}_R=0$.
\end{enumerate}
\end{proof}



\begin{theorem}\label{thm:dos}
  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,
  \begin{equation}
    \label{eq:3}
    F(G+_R H+_S K)=\sum_{A\in \I_G,C\in \I_K}\sum_{B\in \I_H}{\bf
      T}_{G,H}^R(A,B){\bf T}_{H,K}^S(B,C).
  \end{equation}
Furthermore, if $K=G$, then
  \begin{equation}
    \label{eq:4}
    F(G\oplus_R H\oplus_S G)=\sum_{A\in\I_G,B\in\I_H}{\bf
      T}_{G,H}^R(A,B) {\bf T}_{H,G}^S(B,A)\;.
  \end{equation}
\end{theorem}
\begin{proof}
  We have that $J\in\I_{G+_R H+_S K}$ iff there exist $A\in
  \I_G, B\in \I_H,C\in\I_K$ such that $J=A\uplus B\uplus C$ and,  due
  to 
  Lemma \ref{uno}, 
\[
\braket{\vect{\Psi}_{G}(A)}{\vect{\Psi}_{H}(B)}_{R}+\braket{\vect{\Psi}_{H}(B)}{\vect{\Psi}_{K}(C)}_{S}=0
\]
which is equivalent to
\[
\overline{\braket{\vect{\Psi}_{G}(A)}{\vect{\Psi}_{H}(B)}_{R}}\quad\overline{\braket{\vect{\Psi}_{H}(B)}{\vect{\Psi}_{K}(C)}_{S}}=1
\]
so
\[
|\I_{G+_R H+_S K}|=\sum_{\substack{A\in \I_{G},B\in\I_H\\
C\in \I_K}} \overline{\braket{\vect{\Psi}_{G}(A)}{\vect{\Psi}_{H}(B)}_{R}}\quad\overline{\braket{\vect{\Psi}_{H}(B)}{\vect{\Psi}_{K}(C)}_{S}}
\]
from which \eqref{eq:3} follows.

Similarly $J\in\I_{G\oplus_R H\oplus_S G}$ iff there exist $A\in\I_G$ and
$B\in\I_H$ such that  $J=A\uplus B$ and 
$\braket{\vect{\Psi}_{G}(A)}{\vect{\Psi}_{H}(B)}_{R}+\braket{\vect{\Psi}_{H}
(B)}{\vect{\Psi}_{G}(A)}_{S}=0$, since Lemma \ref{uno}. Thus 
\[
\overline{\braket{\vect{\Psi}_{G}(A)}{\vect{\Psi}_{H}(B)}_{R}}\quad\overline{\braket{\vect{\Psi}_{H}
(B)}{\vect{\Psi}_{G}(A)}_{S}}=1
\]
which leads to
\[
|\I_{G\oplus_R H\oplus_S G}|=\sum_{A\in\I_G,B\in\I_H} \overline{\braket{\vect{\Psi}_{G}(A)}{\vect{\Psi}_{H}(B)}_{R}}\quad\overline{\braket{\vect{\Psi}_{H}
(B)}{\vect{\Psi}_{G}(A)}_{S}}\;.
\]
\end{proof}



In fact, the transfer matrix is an actual matrix indexed by the
cartesian product of independent sets $\I_G\times\I_H$. We denote
such matrix by 
\[{\bf T}_{G,H}^R=({\bf T}_{G,H}^R(A,B))_{A\in \I_G,B\in\I_H}.\]
 Note
that ${\bf 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 $\ket{G}$, while $\bra{G}$ is the transpose of $\ket{G}$. Then, Theorem
\ref{thm:dos} ensures that
\begin{equation}
  \label{eq:prodUsual}
F(G+ H+ K )=\bra{G}{\bf T}_{G,H} ^R{\bf T}_{H,K}^S\ket{K},
\end{equation}
furthermore
\begin{equation}
  \label{eq:prodH}
F(G\oplus_R H\oplus_SG)=\bra{G}{\bf T}_{G,H} ^R* ({\bf T}_{H,G}^S)^t\ket{H}
\end{equation}
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 \eqref{eq:prodH} as a standard matrix product
as follows
\begin{equation}
  \label{eq:trace}
F(G\oplus_R H\oplus_SG)= \Tr\big({\bf T}_{G,H} ^R {\bf T}_{H,G}^S\big)  
\end{equation}
where $\Tr$ denotes the matrix trace. 
 However the formula in \eqref{eq:prodH} is less difficult to calculate than  \eqref{eq:trace}, 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  \eqref{eq:prodH} is useful for computer calculation.

A similar formula to \eqref{eq:prodUsual} and \eqref{eq:prodH}, for a
general graph,  was found
by Merrifield and Simmons \cite[p. 209]{Merrifield} 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 \ref{thm:dos} can be
generalized in order to obtain:

\begin{theorem}\label{thm:prod}
  \begin{enumerate}
  \item The number of independent sets of
    $G_1+_{R_1}G_2+_{R_2}\cdots+_{R_{n-1}} G_{n}$ is the
    matrix product $\bra{G_1}{\bf T}_{G_1,G_2}^{R_1}\cdots {\bf T}_{G_{n-1},G_{n}}^{R_{n-1}}\ket{G_n}$.
\item The number of independent sets of
  $G_1\oplus_{R_1}G_2\oplus_{R_2}\cdots\oplus_{R_{n-1}} G_{n}\oplus_{R_n}G_1$
  is the matrix trace $\Tr({\bf T}_{G_1,G_2}^{R_1}\cdots
  {\bf T}_{G_{n-1},G_{n}}^{R_{n-1}}{\bf T}_{G_{n},G_1}^{R_n})$.
  \end{enumerate}
\end{theorem}

Next, the Fibonacci numbers of two classical platonic solid graphs are
calculated using  Theorem \ref{thm:prod}. 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&lt;1$, for any given graph $G$. 

 
\paragraph{Octahedral graph.} Using  the decomposition of the
  octahedral graph as the Zykov sum given in Table \ref{tab:platonic}, we
  get  the following  matrices: 
\[
\bra{C_3}=(1,1,1,1),\quad
{\bf T}_{C_3,C_3}^R=\begin{pmatrix}1&amp;1&amp;1&amp;1\cr 1&amp;0&amp;0&amp;1\cr 1&amp;1&amp;0&amp;0\cr
  1&amp;0&amp;1&amp;0\cr \end{pmatrix}, \quad \ket{C_3}=
\begin{pmatrix}
  1\\
  1\\
1\\
1
\end{pmatrix}.
\]
Thus, from Theorem \ref{thm:prod}, the Fibonacci number of the
octahedral graph is $F(C_3+_R C_3)=\bra{C_3}{\bf T}_{C_3,C_3}^R \ket{C_3}=10$.

\paragraph{Dodecahedral graph.} From Table \ref{tab:platonic},
  we get that the dodecahedral graph $G$ has  Fibonacci number
  $F(G)=\bra{C_5}{\bf T}_{C_5,C_{10}}^{R_1}
\left({\bf T}_{C_5,C_{10}}^{R_2}\right)^t \ket{C_5}=5,828$, 
where 
\[
{\bf T}_{C_5,C_{10}}^{R_1}
\left({\bf T}_{C_5,C_{10}}^{R_2}\right)^t=
\left(\begin{array}{ccccccccccc}
123&amp;89&amp;89&amp;89&amp;65&amp;89&amp;65&amp;65&amp;89&amp;65&amp;65\\
 89&amp;55&amp;63&amp;64&amp;40&amp;63&amp;39&amp;45&amp;55&amp;39&amp;40\\
 89&amp;55&amp;55&amp;63&amp;39&amp;64&amp;40&amp;40&amp;63&amp;39&amp;45\\
 89&amp;63&amp;55&amp;55&amp;39&amp;63&amp;45&amp;39&amp;64&amp;40&amp;40\\
65&amp;39&amp;39&amp;40&amp;24&amp;45&amp;27&amp;27&amp;40&amp;24&amp;25\\
 89&amp;64&amp;63&amp;55&amp;40&amp;55&amp;40&amp;39&amp;63&amp;45&amp;39\\
 65&amp;40&amp;45&amp;40&amp;25&amp;39&amp;24&amp;27&amp;39&amp;27&amp;24\\
65&amp;40&amp;39&amp;39&amp;24&amp;40&amp;25&amp;24&amp;45&amp;27&amp;27\\
 89&amp;63&amp;64&amp;63&amp;45&amp;55&amp;39&amp;40&amp;55&amp;40&amp;39\\
 65&amp;39&amp;40&amp;45&amp;27&amp;40&amp;24&amp;25&amp;39&amp;24&amp;27\\
 65&amp;45&amp;40&amp;39&amp;27&amp;39&amp;27&amp;24&amp;40&amp;25&amp;24
\end{array}\right)\;.
\]  










\section{The series of independent sets}\label{sec:series}
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\in \N}$ of graphs.
\begin{definition}
  We call  the infinite series
  \begin{equation}
    F_\G(x)=F(G_0)+F(G_1) x+F(G_2)x^2+\cdots
  \end{equation}
 the {\it Fibonacci series of  $\G$.}
\end{definition}


The following families, which contain repetitive patterns of open and
closed Zykov sums, include many
interesting cases such as grids, tori, cylinders \cite{Calkin,Euler,Golin} and so on.

\begin{definition}\label{def:fam}
Let $\G=(G_n)_{n\geq 0}$ be a family of graphs. We call $\G$ a family of:
  \begin{enumerate}
  \item\label{def:uno} {\it Strip graphs} if there exists  a graph $G$ such that
    $G_0=G$, $G_1=G+_RG$, $G_2=G+_RG+_R G,\ldots$ .  
\item\label{def:dos} {\it Ring graphs} if there exists a graph $G$ such that $G_0=G$,
  $G_1=G\oplus_S G$,
  $G_2=G\oplus_RG\oplus_SG, G_3=G\oplus_RG\oplus_RG\oplus_SG,\ldots$
  . 
  In such a case  $G+_SG$ is called the {\it skewing}
  of $\G$. 
\item {\it 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+_RG+_{R^{-1}}G+_RG,
  \ldots$ . 
\item {\it Alternating ring graphs} if there exists  a graph $G$ such
  that  $G_0=G$,
  $G_1=G\oplus_R G$, $G_2=G\oplus_R G\oplus_{R^{-1}}G$,
  $G_3=G\oplus_RG\oplus_{R^{-1}}G\oplus_RG, \ldots$ . 
\end{enumerate}
In any case $G$ is called the {\it shape} of $\G$ and  $G+_R G$ is called the {\it fundamental pattern} of $\G$.
\end{definition}

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 \ref{def:fam} have Fibonacci series with minor variations
of the geometric series. 

\begin{theorem}\label{thm:main}
  Let $\G$ be a family of graphs as in Definition \ref{def:fam}. Let
  $G$ be the shape of $\G$, ${\bf T}$ the transfer matrix of the fundamental
  pattern and  ${\bf I}$  the
identity matrix. 
  \begin{enumerate}
  \item If $\G$ is a family of strip graphs  then
    \begin{equation}
      \label{eq:8}
      F_\G(x)=\bra{G}({\bf I}-x {\bf T})^{-1}\ket{G}.
    \end{equation}
\item If $\G$ a family of  ring graphs then
  \begin{equation}
    \label{eq:9}
    F_\G(x)=F(G)+\Tr\left({x}({\bf I}-x {\bf T})^{-1} {\bf T}_1\right)
  \end{equation}
where ${\bf T}_1$ is the transfer matrix of the skewing of $\G$.
 \end{enumerate}
\end{theorem}
\begin{proof}
  \noindent
  \begin{enumerate}
  \item From Theorem \ref{thm:prod}, we get, for any $n$ non-negative
    integer, $F(G_n)=\bra{G} {\bf T}^n\ket{G}$. So
\[
F_\G(x)=\bra{G}\sum_{n=0}^\infty {\bf T}^nx^n\ket{G}=\bra{G}({\bf
  I}-x{\bf T})^{-1}\ket{G}.
\]
\item Similarly, from Theorem \ref{thm:prod}, we have
  $F(G_n)=\Tr\big({\bf T}^{n-1} {\bf T}_1\big)$, $n\geq 1$. Then
  \begin{eqnarray*}
F_\G(x)&amp;=&amp;F(G)+\sum_{n=1}^\infty \Tr\big({\bf T}^{n-1}
  {\bf T_1}\big) x^n \\
&amp;=&amp;F(G)+\Tr\left({x}({\bf I}-x {\bf T})^{-1} {\bf T}_1\right)
  \end{eqnarray*}
due to the linearity of the matrix trace. 
  \end{enumerate}
\end{proof}

Similarly, we can prove the following.

\begin{theorem} Under the notation given in Theorem \ref{thm:main}.
  \begin{enumerate}
  \item   If $\G$ is a family of  alternating strip graphs then 
    \begin{equation}
      \label{eq:alter}
F_\G(x)=\bra{G}({\bf I}-x^2{\bf T} {\bf T}^t)^{-1}({\bf I}+x{\bf T})\ket{G}.    
    \end{equation}
\item If $\G$ is a family of  alternating ring graphs then 
\[
F_\G(x)=\Tr\big(({\bf I}-x^2 {\bf T} {\bf T}^t)^{-1}({\bf I}+x{\bf T})\big).
\]
\end{enumerate}
\end{theorem}

\section{Examples}\label{sec: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\"obius strips, nanotori, and tori
with Petersen graph shape.


\paragraph{Centipedes.}
Now, our fundamental pattern is $P_2+_f P_2$ given in Figure 
\ref{fig:centipedeFun} where the partial function
$f:\{0,1\}\rightarrow\{0,1\}$ is defined just by $f(0)=0$.
\begin{figure}[thb]
  \begin{center}
  \includegraphics[scale=1]{centipede.eps}
 \end{center}
 \caption{Fundamental pattern of the centipedes}
   \label{fig:centipedeFun}
\end{figure}
Next, we take the family of strip graphs $\G=(G_n)_{n\geq 0}$ given by
open Zykov sums 
$G_n=P_2+_f\cdots +_fP_2$, where the number of $P_2$ is $n+1$, $n=0,1,\ldots$ Then, the transfer matrix of
$P_2+_{f}P_2$ is
\begin{equation}
  \label{eq:7}
{\bf T}_{P_2,P_2}^f=
\begin{pmatrix}
  1 &amp; 1 &amp; 1\\
  1 &amp; 0 &amp; 1\\
   1 &amp; 1 &amp; 1
\end{pmatrix}.
\end{equation}
Then, from \eqref{eq:8}, 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
\seqnum{A028859} in \cite{OEIS}.


  
\paragraph{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  
  \ref{fig:accordion} 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  \ref{fig:caterRel}).

\begin{figure}[t]
\begin{center}
  \includegraphics[scale=.5]{3xn.eps}
 \end{center}
\caption{Strip of graphs with fundamental pattern $P_3+_R P_3$}
    \label{fig:accordion}
\end{figure}  


  \begin{figure}[b]
\begin{center}
  \includegraphics[scale=1]{3xnA.eps}
 \end{center}
    \caption{The fundamental pattern $P_3+_R P_3$}
    \label{fig:caterRel}
  \end{figure}
Its
transfer matrix is
\[
{\bf T}^R_{P_3,P_3}=\begin{pmatrix}
  1&amp;1&amp;1&amp;1&amp;1\cr 1&amp;1&amp;0&amp;1&amp;1\cr 1&amp;1&amp;1&amp;0&amp;0\cr 1&amp;1&amp;1&amp;1&amp;1\cr 1&amp;1&amp;0&amp;
 1&amp;1\cr 
\end{pmatrix}.
\]
From \eqref{eq:8} 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 \seqnum{A188707}.
Similarly, we have that the family of graphs $\mathcal{R}$ given in
Figure  \ref{fig:caterPaste}
\begin{figure}
\begin{center}
  \includegraphics[scale=.5]{3xnB.eps}
 \end{center}
  \caption{A generic element of  the family $\mathcal{R}$}
  \label{fig:caterPaste}
\end{figure}
is a family of ring graphs with fundamental pattern and skewing
$P_3+_R P_3$. From \eqref{eq:9} we have that its Fibonacci series
is
\[
F_{\mathcal{R}}(x)=\frac{9\,x^2-20\,x+5}{3\,x^2-5\,x+1}\;.
\]


\paragraph{Cylinders.} Let $C_i$ be the $i$-cycle graph  and
$P_n$ be the path graph with $n$ vertices.  Let
$\Id:V(C_i)\rightarrow V(C_i)$ be the identity map. Then, the cylinder $C_i\times P_n$
is $G(i,n)=C_i+_{\Id} C_i+_{\Id}\cdots+_{\Id} C_i$, where the number
of cycles is $n+1$, $n\geq 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 \eqref{eq:8}, for some fixed $i$, we can calculate the generating
function $F_{G(i,*)}(x)$, as shown in Table \ref{tab:cyl}.

\begin{table}[ht]
  \begin{center}
\begin{tabular}{ccc}
\hline\noalign{\smallskip}
 $i$ &amp; $F_{G(i,*)}(x)$ &amp; Sequence \\
\noalign{\smallskip}\hline\noalign{\smallskip}
$2$ &amp; $-\frac{x+3}{x^2+2\,x-1}$ &amp; \seqnum{A078057}\\
 $3$ &amp; $-\frac{x+4}{x^2+3x-1}$ &amp;\seqnum{A003688}\\
  $4$ &amp; $-\frac{x^2-7}{x^3-x^2-5x+1}$ &amp;\seqnum{A051926}\\
$5$ &amp;
$-\frac{x^2-4x-11}{x^3-5x^2-7x+1}$ &amp; \seqnum{A181989} \\
$6$ &amp; $-\frac{x^4-x^3-25x^2-17x+18}{x^5-2x^4-25x^3-3x^2+12x-1}$ &amp;\seqnum{A181961}\\
$7$ &amp; $-\frac{x^4+6x^3-38x^2-16x+29}{x^5+5x^4-44x^3+8x^2+17x-1}$ &amp;\seqnum{A182014} \\
$8$ &amp;
$-\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}$
&amp; \seqnum{A182019}\\
\noalign{\smallskip}\hline
\end{tabular}
 \end{center}
\caption{The Fibonacci series of some cylinders. These are the
  generating functions of the integer sequences in the third column
  except for the first term}  
\label{tab:cyl}
\end{table}


\paragraph{Tori.}
Let $C_i$ be the cycle graph of length $i$. Then
$G(i,n)=C_i\oplus_{\Id} C_i\oplus_{\Id}\cdots\oplus_{\Id} C_i\oplus_{\Id} C_i$
where the number of cycles written is $n+1$, $n=0,1,\ldots$. Such graph is the torus
$C_i\times 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 \eqref{eq:9}, as shown in Table \ref{tab:tori}.

\begin{table}[ht]
  \begin{center}
\begin{tabular}{lll}
\hline\noalign{\smallskip}
$i$ &amp; $F_{G(i,*)}(x)$ &amp; Sequence\\
\noalign{\smallskip}\hline\noalign{\smallskip}
$3$ &amp;${\frac{5\,x^2+7\,x-4}{x^3+4\,x^2+2\,x-1}}$ &amp; \seqnum{A051928}\\
$4$
&amp;$-{\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}}$ &amp; \seqnum{A050402}\\
$5$ &amp;
$-{\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}}$ &amp;\seqnum{A182041}
\\
$6$ &amp;
$-p(x)/q(x)$ &amp;\seqnum{A182052}
\\
\noalign{\smallskip}\hline
\end{tabular}
\end{center}
\caption{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$}
  \label{tab:tori}
\end{table}




\paragraph{Generalized Petersen graphs.} We are
  dealing with generalized Petersen graphs  $P(i,2)$
  defined by  $V(P(i,2))=\{0,1,\ldots,2i-1\}$ and
  \begin{multline*}
  E(P(i,2))=\big\{\{j,j+i\}\,|\,0\leq j\leq
  i-1\big\}\cup\big\{\{j,k\}\,|\,j-k\equiv 0\pmod{2} \text{ and }
  i\leq  j,k&lt;2i\big\}\\\cup\big\{\{j,k\}\,|\,k\equiv j+1\pmod{i}\text{
    and }0\leq j,k\leq i-1\big\} .
\end{multline*}
The Fibonacci number
  for generalized Petersen graphs $P(i,2)$ with $i$  an odd number was calculated by Wagner \cite{Wagner}. 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  \ref{fig:petersenFun}).
  \begin{figure}[th]
\begin{center}
  \includegraphics[scale=1]{petersen.eps}
 \end{center}
        \caption{Fundamental pattern in the Petersen graphs $P(2i,2)$}
    \label{fig:petersenFun}
  \end{figure}

Then, the ring graph family with
  shape $P_4$, 
  fundamental pattern $P_4+_R P_4$ and skewing the same
  $P_4+_RP_4$, is the family of generalized Petersen
  graphs $\mathcal{G}=\big(P(2i,2)\big)_{i\geq 0}$:
\[
P(2i,2)= P_4\oplus_R P_4\oplus_R\cdots \oplus_R P_4\oplus_R P_4,
\]
where $P_4$ appears $i+1$ times, $i=0,1,\ldots$. Note that we included the
non-standard generalized Petersen graphs $P(0,2)=P_4$ and the
multigraph $P(2,2)=P_4\oplus_RP_4$.
\begin{figure}[hb]
\begin{center}
  \includegraphics[scale=.7]{petersenGen.eps}
 \end{center}
  \caption{Generalized Petersen graph $P(2i,2)$.}
  \label{petersenGen}
\end{figure}


The related transfer matrix is
\begin{equation}
  \label{eq:11}
  {\bf T}^R_{P_4,P_4}=\begin{pmatrix}1&amp;1&amp;1&amp;1&amp;1&amp;1&amp;1&amp;1\cr 1&amp;0&amp;1&amp;1&amp;0&amp;1&amp;0&amp;1\cr 1&amp;1&amp;1&amp;0&amp;0&amp;1&amp;1&amp;1\cr 1
 &amp;1&amp;1&amp;1&amp;1&amp;1&amp;1&amp;1\cr 1&amp;0&amp;1&amp;1&amp;0&amp;1&amp;0&amp;1\cr 1&amp;1&amp;1&amp;1&amp;1&amp;0&amp;0&amp;0\cr 1&amp;0&amp;1&amp;1&amp;0&amp;0&amp;
 0&amp;0\cr 1&amp;1&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0\cr \end{pmatrix}.
\end{equation}
Then, from \eqref{eq:9}, we get
\[
F_\G(x)=\frac{\left( 6\,{x}^{2}-11\,x-8\right) \,\left( 2\,{x}^{3}-5\,{x}^{2}-4\,x+1\right) }{4\,{x}^{5}-13\,{x}^{4}+3\,{x}^{3}+15\,{x}^{2}+3\,x-1}
\]
which is the generating function of \seqnum{A182054}.


For generalized Petersen graphs of the type $P(2i+1,2)$, $i\geq 2$ we take the
family $\mathcal{P}$ given in Figure  \ref{fig:petersenOdd}, i.e., 
\[
P(2i+1,2)={\bigoplus_{R_1}}_{k=1}^{i-1} P_4\oplus_{R_2} M\oplus_{R_3} P_4
\]
where $M$ is the graph such that $V(M)=\{0,1,2,3,4,5\}$,
$E(M)=\big\{\{0,1\},\{1,2\},\{2,3\},$ $\{2,4\}, \{4,5\},\{0,5\}\big\}$
and relations
$R_1=\big\{(0,0),(3,3),(2,1)\big\}$, $R_2=\big\{(0,0),(3,3),(2,1)\big\}$, $R_3=\{(3,0),(5,3),(4,1)\}$.
\begin{figure}[th]
\begin{center}
  \includegraphics[scale=.7]{petersenGenOdd.eps}
 \end{center}
  \caption{The family of graphs $P(2i+1,2)$}
  \label{fig:petersenOdd}
\end{figure}

From the
Theorem \ref{thm:prod} and proof of   \eqref{eq:9} in Theorem \ref{thm:main}, we get
\[
F_\mathcal{P}(x)=\sum_{j=0}^\infty \Tr({\bf T}_1^j {\bf T}_2
{\bf T}_3)
x^j=\Tr\left(({\bf I}-x{\bf T}_1)^{-1} {\bf T}_2{\bf T}_3\right)\]
where 
 ${\bf T}_1={\bf T}_{P_4,P_4}^{R_1}$ is given by \eqref{eq:11}; while 
 ${\bf T}_2={\bf T}_{P_4,M}^{R_2}$ and  ${\bf T}_3={\bf T}_{M,P_4}^{R_3}$ are $8\times 19$ and
 $19\times 8$ matrices respectively. 
Thus,
\[
F_\mathcal{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 \seqnum{A182077} with a shift  of one
 term.
\paragraph{Families with Petersen graph shape.} Let
  $\Id:V(P(5,2))\rightarrow 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\geq 0}$ where $G_n=P(5,2)+_{\Id}P(5,2)+_{\Id}\cdots
+_{\Id} P(5,2)$ with $n+1$ copies of the Petersen graph, $n\geq 0$ (see
Figure ~\ref{fig:tubePetersen}). Then, the transfer matrix
${\bf T}_{P(5,2),P(5,2)}^{\Id}$ is a $76\times 76$-matrix, since
$F(P(5,2))=76$. 
  \begin{figure}[bh]
\begin{center}
\includegraphics[scale=1.4]{nanoPet.eps}
\end{center}
    \caption{A strip graph with shape $P(5,2)$, the Petersen
      graph. The edges given by the identity map are shown by dotted lines}
    \label{fig:tubePetersen}
  \end{figure}

From \eqref{eq:8} 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 \eqref{eq:9},  that its Fibonacci series $F_{\G'}(x)$ satisfies 
 $F_{\G'}(x)=p(x)/q(x)$ where
 \begin{multline*}
   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
\end{multline*}
and
\begin{multline*}
  q(x)=\left(x-1\right)\,\left(x^2+2\,x-1\right)\,\left(x^5+5\,x^4-4\,x^3-
 14\,x^2+3\,x+1\right)\,\\\left(x^6+11\,x^5-137\,x^4+172\,x^3+215\,x^2+
 39\,x-1\right)\,\\\left(x^7+4\,x^6-52\,x^5-105\,x^4+51\,x^3+78\,x^2-10
 \,x-1\right)\;.
\end{multline*}
\begin{figure}[tbh]
  \begin{center}
\includegraphics[scale=1.6]{petersenRing.eps} \qquad  \includegraphics[scale=1.6]{twistPet.eps} 
  \end{center}
\caption{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=\left \{\left( 0 , 1 \right)  , \left( 1 , 2 \right)  , \left( 2 , 
 3 \right)  , \left( 3 , 4 \right)  , \left( 4 , 0 \right)  , \left( 
 5 , 6 \right)  , \left( 6 , 7 \right)  , \left( 7 , 8 \right)  , 
 \left( 8 , 9 \right)  , \left( 9 , 5 \right)  \right \}$. The former
ring has Fibonacci number  27,053,615,385,404,201. The latter has
Fibonacci number  27,050,814,022,108,001.}
\label{k77}
\end{figure}

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\pi/5$. More formally, we take $V(P(5,2))=\{0,1,2,\ldots, 9\} $ as
the vertices set of the Petersen graph, and 
\begin{multline*}
E(P(5,2))=\left \{\left\{ 0
    , 1 \right\}  , \left\{ 0 , 4 \right\}  , \left\{ 0 , 5 \right\}  ,
  \left\{ 1 , 2 \right\}  , \left\{ 1 , 6 \right\}  , \left\{ 2 , 3 \right\}
  , \left\{ 2 , 7 \right\}  , \left\{ 3 , 4 \right\}  ,\right.\\\left. \left\{ 3 , 8
  \right\}  , \left\{ 4 , 9 \right\}  , 
\left\{ 5 , 7 \right\},
 \left\{ 5 , 8 \right\}  , \left\{ 6 , 8 \right\}  , \left\{ 6 , 9 \right\}
 , \left\{ 7 , 9 \right\}  \right \}.
\end{multline*}
Then, the new skewing induced by $R$ is defined as follows (see Figure 
\ref{k77}) 
\[
  R=\left \{\left( 0 , 1 \right)  , \left( 1 , 2 \right)  , \left( 2 , 
 3 \right)  , \left( 3 , 4 \right)  , \left( 4 , 0 \right)  , \left( 
 5 , 6 \right)  , \left( 6 , 7 \right)  , \left( 7 , 8 \right)  , 
 \left( 8 , 9 \right)  , \left( 9 , 5 \right)  \right \}.
\] 
Then $F_{\G''}(x)=p_1(x)/q_1(x)$, where
\begin{multline*}
  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
\end{multline*}
and
\begin{multline*}
  q_1(x)=\left(x^2+2\,x-1\right)\,\left(x^6+11\,x^5-137\,x^4+172\,x^3+215\,x^2+39\,x-1\right)\,\\\left(x^7+4\,x^6-52\,x^5-105\,x^4+51\,x^3+78\,x^2-10\,x-1\right).
\end{multline*}
\paragraph{Armchair  nanotube graphs.} Let $B_n$ be the graph
  with $2n$ vertices $\{0,1,\ldots,$ $2n-1\}$ and set of edges
  $\{\{0,1\},\{2,3\},\ldots,\{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+_\varnothing\cdots+_\varnothing P_2.
\]
We define a relation map $R:V(B_n)\rightarrow V(B_n)$ as
$R(i)=(i-1)\bmod{2n}$, $i=0,\ldots,2n-1$. An {\it armchair nanotube
  graph} of {\it length $n$} and {\it breadth $k$} is
\[
NT_{n,k}=B_n+_R B_n+_{R^{-1}} B_n+_R\cdots+_{R^{\pm 1}}B_n
\]
where $B_n$ appears $k+1$ times, $k\geq 0$ (this graph forms the structure of the
$(n,n)$ armchair carbon nanotube \cite{nano} without caps).  Thomassen
\cite{Thomassen} defines a similar graph called  {\it hexagonal
  cylinder circuit}, however this belongs to a different family of
nanotubes: {\it zig-zag carbon nanotubes}. 

By definition $NT_{n,*}=\big(NT_{n,k}\big)_{k\geq
  0}$ is a  family
of 
alternating strip graphs with fundamental pattern
$B_n+_RB_n$. By \eqref{eq:alter} 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 \seqnum{A182130}.


Similarly, a {\it nanotorus graph} is the following closed Zykov sum:
\[
N\tau_{n,k}=B_n\oplus_R B_n\oplus_{R^{-1}} B_n+_R\cdots\oplus_{R^{\pm 1}}B_n,
\]
where, again, $B_n$ appears $k+1$ times, $k\geq 0$. Now the family
$N\tau_{3,*}=(N\tau_{3,k})_{k\geq 0}$ has Fibonacci series
$F_{N\tau_{3,*}}(x)=p(x)/q(x)$, where
\begin{multline*}
  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
\end{multline*}
and
\begin{multline*}
q(x)=\left(x-1
 \right)\,\left(x+1\right)\,\left(3\,x^3-5\,x^2-5\,x+1\right)\,\left(
 36\,x^4-x^3-20\,x^2-x+1\right)\,\\\left(36\,x^4+x^3-20\,x^2+x+1\right)
 \,\left(28\,x^5+42\,x^4-109\,x^3+17\,x^2+13\,x-1\right).
\end{multline*}

The rational function $F_{N\tau_{3,*}}(x)$ is the generating function of
the sequence \seqnum{A182141}.


\begin{figure}[th]
  \begin{center}
  \includegraphics[scale=1.3]{nanotube.eps}
\qquad
\includegraphics[scale=1.3]{nanotubeRing.eps}
  \end{center}
  \caption{The nanotube graph $NT_{5,21}$ on the left and the
    nanotorus graph $N\tau_{5,21}$ on the right. Once again, the edges given by the
    relation set are shown by dotted lines. Using Theorem
    \ref{thm:prod}  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\tau_{5,21}$ has Fibonacci number 73,562,247,493,061,556,896,479,759,292,362,159,745}
  \label{fig:nanotube}
\end{figure}


\paragraph{Generalized M\"obius Ladders.} Let $P_n$ be the
  path graph with $n$ vertices, $V(P_n)=\{0,\ldots,n-1\}$, $\sigma$ be
  a permutation of $V(P_n)$ and $\Id$ be the identity map on $V(P_n)$. Then a generalized M\"obius ladder
  $M(n,m,\sigma)$ is
\[
M(n,m,\sigma)=P_n\oplus_{\Id}\cdots\oplus_{\Id} P_n\oplus_\sigma P_n
\]
where $P_n$ appears $m+1$ times, $m=0,1,\ldots$; for instance, if
$\sigma:V(P_2)\rightarrow V(P_2)$ is the transposition $\sigma(0)=1$
and $\sigma(1)=0$ then $M(2,*,\sigma)=(M(2,m,\sigma))_{m\geq 0}$ is the family of
usual M\"obius ladders. The family of ring graphs $M(2,*,\sigma)$ has fundamental pattern $P_2+_{\Id} P_2$
and skewing $P_2+_\sigma  P_2$. We have the transfer matrices,
\[
{\bf T}^{\Id}_{P_2,P_2}=
\begin{pmatrix}
 1&amp;1&amp;1\cr 1&amp;0&amp;1\cr 1&amp;1&amp;0\cr 
\end{pmatrix},\quad {\bf T}^\sigma_{P_2,P_2}=
\begin{pmatrix}
1&amp;1&amp;1\cr 1&amp;1&amp;0\cr 1&amp;0&amp;1\cr 
\end{pmatrix}.
\]
Then, from \eqref{eq:9}, we get
\[
F_{M(2,*,\sigma)}(x)=\frac{2\,{x}^{3}+7\,{x}^{2}-3}{\left( x+1\right) \,\left( {x}^{2}+2\,x-1\right) }
\]
which is the generating function of \seqnum{A182143} except for the
first term.



Now, we take families
$M(3,*,\sigma_i)=\left(M(3,m,\sigma_i)\right)_{m\geq 0}$, $i=1,2,3$ 
with $\sigma_1,\sigma_2,\sigma_3$ permutations of $V(P_3)$ defined in
Figure  \ref{fig:permutations}.  Thomassen \cite{Thomassen} calls the
family of graphs  $M(3,\sigma_2)$  {\it quadrilateral M\"obius double
  circuits}. 


We have
\[
{\bf T}^{\sigma_1}_{P_3,P_3}=
\begin{pmatrix}1&amp;1&amp;1&amp;1&amp;1\cr 1&amp;0&amp;1&amp;1&amp;0\cr 1&amp;1&amp;1&amp;0&amp;0\cr 1&amp;1&amp;0&amp;1&amp;1\cr 1&amp;0&amp;0&amp;
 1&amp;0\cr 
\end{pmatrix},\quad
{\bf T}^{\sigma_2}_{P_3,P_3}=
\begin{pmatrix}
 1&amp;1&amp;1&amp;1&amp;1\cr 1&amp;1&amp;1&amp;0&amp;0\cr 1&amp;1&amp;0&amp;1&amp;1\cr 1&amp;0&amp;1&amp;1&amp;0\cr 1&amp;0&amp;1&amp;
 0&amp;0\cr 
\end{pmatrix},
\]
\[
{\bf T}^{\sigma_3}_{P_3,P_3}=
\begin{pmatrix}
 1&amp;1&amp;1&amp;1&amp;1\cr 1&amp;1&amp;0&amp;1&amp;1\cr 1&amp;1&amp;1&amp;0&amp;0\cr 1&amp;0&amp;1&amp;1&amp;0\cr 1&amp;0&amp;0&amp;
 1&amp;0\cr 
\end{pmatrix},\quad
{\bf T}^{\Id}_{P_3,P_3}=
\begin{pmatrix}
  1&amp;1&amp;1&amp;1&amp;1\cr 1&amp;0&amp;1&amp;1&amp;0\cr 1&amp;1&amp;0&amp;1&amp;1\cr 1&amp;1&amp;1&amp;0&amp;0\cr 1&amp;0&amp;1&amp;
 0&amp;0\cr 
\end{pmatrix}.
\]
Then
\begin{multline*}
F_{M(3,*,\sigma_1)}(x)=\frac{3\,x^5+6\,x^4-19\,x^3-30\,x^2-2\,x+5}{\left(x+1\right)\,
 \left(x^4-6\,x^2-2\,x+1\right)}, \\F_{M(3,*,\sigma_2)}(x)=\frac{2\,x^5+x^4-24\,x^3-28\,x^2-2\,x+5}{\left(x+1\right)\,\left(x
 ^4-6\,x^2-2\,x+1\right)},
\end{multline*}
and
\[
F_{M(3,*,\sigma_3)}(x)=\frac{4\,x^5+6\,x^4-25\,x^3-32\,x^2-x+5}{\left(x+1\right)\,\left(x
 ^4-6\,x^2-2\,x+1\right)}.
\]


\begin{figure}[th]
  \begin{center}
\includegraphics{sigma1.eps}
  \end{center}
  \caption{A subset of permutations of $V(P_3)$}
  \label{fig:permutations}
\end{figure}


\paragraph{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,\ldots, n-1\}$ and $E(B_n)=\varnothing$. Let
  $R$ be the relation on $V(B_n)$ given by $i R i$ and $iR j$ where
  $j\equiv i-1$ (mod ${n}$), $i=0,\ldots 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+_RB_n+_R\cdots+_R B_n
\]
\[
R_n^{k+1}=C_n+_RB_n+_R\cdots+_R B_n+_R C_n
\] 
where $B_n$ appears $k-1$ times, $k=1,2,\ldots$ and
$G_n^0=R_n^0=\varnothing$ the empty graph, $R^{1}_n=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,\ldots,n-1\}$. Also, we define
\[
K_n^k=C_n'+_R\cdots+_R C_n'+_R K_n
\]
\[
P_n^{k+1}=K_n+_R C_n'+_R\cdots+_R C_n'+_R K_n
\]
where $C_n'$ appears $k-1$ times, $k=1,2,\ldots$ and
$K_n^0=P_n^0=\varnothing$, $P_n^{1}=K_n$.
The graphs
$G_{n}^k,R_n^k,K_n^k$ and $P_n^k$ are called   {\it (almost) regular graphs}
class 1, class 2, class 3 and class 4, respectively by Burstein,
Kitaev,  and
Mansour \cite{Burstein}. 
Thus, from Theorem \ref{thm:prod}, we get
\begin{equation}
  \label{eq:6}
F_{G_n^*}(x)=1+F(C_n)\,x+\bra{C_n}{\bf T}_{C_n,B_n}^R({\bf I}-x\,
{\bf T}_{B_n,B_n}^R)^{-1}\ket{B_n}\,x^2,
\end{equation}
\begin{equation}
  \label{eq:10}
F_{R_n^*}(x)=1+F(C_n)\,x
+\bra{C_n} \left(x^2\,{\bf T}^R_{C_n,C_n}+x^3\,{\bf
    T}^R_{C_n,B_n}({\bf I}-x\, {\bf T}_{B_n,B_n}^R)^{-1}{\bf T}^R_{B_n,C_n}\right)\ket{C_n},
\end{equation}
\begin{equation}
  \label{eq:12}
F_{K_n^*}(x)=1+(n+1)\,x+\bra{C_n'}({\bf I}-x\,{\bf
  T}^R_{C_n',C_n'})^{-1} {\bf T}_{C_n',K_n}^R\ket{K_n}\,x^2,  
\end{equation}
\begin{equation}
  \label{eq:13}
F_{P_n^*}(x)=1+(n+1)\,x
+\bra{K_n}\left(x^2\,{\bf T}_{K_n,K_n}^R+x^3\,{\bf
    T}_{K_n,C_n'}^R({\bf I}-x\,{\bf T}_{C_n',C_n'}^R)^{-1}{\bf T}_{C_n',K_n}^R\right)\ket{K_n}.
\end{equation}
Burstein et al \cite{Burstein} 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
\seqnum{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 \cite{Burstein}, respectively. As a consequence, since $77$
does not appear in \seqnum{A007483},   Burstein et al \cite{Burstein} are
wrongfully relating this sequence to the class 4 graphs. The correct
Fibonacci series, after the formulas \eqref{eq:10}, \eqref{eq:12} and
\eqref{eq:13}  are shown in Tables \ref{tab:rn} and \ref{tab:pn}.  


\begin{table}[th]
  \begin{center}
\begin{tabular}{ll|l c}
\hline\noalign{\smallskip}
$n$ &amp; $F_{R_n^*}(x)$ &amp; $F_{K_n^*}(x)$ &amp; Sequence\\
\noalign{\smallskip}\hline\noalign{\smallskip}
$3$ &amp; $-\frac{4\,x^2-1}{2\,x^2-4\,x+1}$ &amp; $\frac{1}{2\,x^2-4\,x+1}$ &amp; \seqnum{A007070}\\
$4$ &amp;$\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}$ &amp; $\frac{3\,x^2+2\,x+1}{x^3-7\,x^2-3\,x+1}$\\
$5$ &amp;$\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}$&amp;$\frac{4\,x^2+x+1}{x^3-7\,x^2-5\,x+1}$ \\
$6$ &amp; $\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}$&amp;$\frac{5\,x^2+1}{x^3-7\,x^2-7\,x+1}$\\
\noalign{\smallskip}\hline
\end{tabular}
  \end{center}
  \caption{Some Fibonacci series of classes 2 and 3 graphs}
  \label{tab:rn}
\end{table}




Due to Theorem \ref{thm:main}, the  family $\varnothing,C_3,C_3+_R C_3,C_3+_R C_3+_R
C_3,\ldots$ has Fibonacci series $(2\,x+1)/(2\,{x}^{2}+2\,x-1)$ which
is the generating function of \seqnum{A026150}; while the family
$\varnothing, K_4,K_4+_RK_4,K_4+_R K_4+_RK_4,\ldots$ has Fibonacci
series $-(2\,x+1)/(2\,x^2+3\,x-1)$ which is the generating function of \seqnum{A007483}. 



\begin{table}[ht]
  \begin{center}
\begin{tabular}{llc}
\hline\noalign{\smallskip}
 $n$ &amp; $F_{P_n^*}(x)$ &amp; Sequence \\
\noalign{\smallskip}\hline\noalign{\smallskip}
$3$ &amp;
$-\frac{\left(2\,x-1\right)\,\left(2\,x+1\right)}{2\,x^2-4\,x+1}$ &amp; \seqnum{A161941}\\
$4$ &amp; $-\frac{8\,x^3+5\,x^2-2\,x-1}{x^3-7\,x^2-3\,x+1}$\\
$5$ &amp;  $-\frac{10\,x^3+11\,x^2-x-1}{x^3-7\,x^2-5\,x+1}$\\
$6$ &amp; $-\frac{12\,x^3+19\,x^2-1}{x^3-7\,x^2-7\,x+1}$\\
\noalign{\smallskip}\hline
\end{tabular}
\caption{Some Fibonacci series of the class 4 graphs. The series
  $F_{P_3^*}(x)$ is the generating function of two times the terms
in  \seqnum{A161941} except the first one}
  \label{tab:pn}
  \end{center}
\end{table}

\section{Acknowledgements}
The authors would like to thank Luke Goodman for helpful comments and suggestions. 

\begin{thebibliography}{99}

\bibitem{Burstein}  A. Burstein,  S.  Kitaev, and  T.  Mansour, 
Counting  independent sets in some classes of (almost) regular graphs,
  {\it Pure Math. Appl. (PU.M.A.)} \textbf{19} (2008), 17--26. 

\bibitem{Calkin} N. Calkin and H. S.  Wilf, 
The number of independent sets in a grid graph, 
{\it SIAM J. Discrete Math.} \textbf{11} (1997), 54--60. 

\bibitem{Carroll} T. Carroll, D. Galvin, and  P. Tetali, 
Matchings and  independent sets of a fixed size in regular graphs, 
    {\it J. Combin. Theory Ser. A}  \textbf{116} (2009), 1219--1227.  

\bibitem{Cutler} J. Cutler and  A.  J. Radcliffe, Extremal graphs for
  homomorphisms, {\it J. Graph Theory} \textbf{67} (2011), 261--284.

\bibitem{Diestel}  R. Diestel, 
{\it Graph Theory}, Springer,  2006.


\bibitem{Engel} K. Engel, 
On the Fibonacci number of an $m\times n$ lattice,
  {\it Fibonacci Quart.} \textbf{28} (1990), 72--78.

  
\bibitem{Euler} R. Euler, The Fibonacci number of a grid graph and a
  new class of integer sequences, {\it J. Integer Seq.} \textbf{8}
 (2005),  Article 05.2.6. 

\bibitem{Galvin} D. Galvin, Two problems on independent sets in
  graphs, {\it Discrete Math.} \textbf{311} (2011), 2105--2112.

\bibitem{Galvin2} D. Galvin and  Y. Zhao, 
The number of independent sets in a graph with small maximum degree,
  {\it Graphs Combin.} \textbf{27}, (2011) 177--186.  

\bibitem{Golin}   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.,  {\it 
Proceedings of the
  Second Workshop on Analytic Algorithmics and Combinatorics
  (ANALCO05)}, SIAM, 2005, pp. 250--258. 

\bibitem{Knop} A. Knopfmacher, R. F. Tichy, S. Wagner, and  V. Ziegler, 
Graphs, partitions and Fibonacci numbers, 
{\it Discrete Appl. Math.} \textbf{155} (2007), 1175--1187. 

\bibitem{Merrifield} R. E.  Merrifield and H. E. Simmons, 
{\it    Topological Methods in Chemistry}, Wiley, 1989.

\bibitem{Pedersen} A. S. Pedersen and   P. D. Vestergaard,
The number of independent sets in unicyclic graphs,  
{\it Discrete Appl. Math.} \textbf{152} (2005), 246--256. 

\bibitem{nano} C. P. Poole, Jr. and   F. J. Owens, 
 {\it Introduction to   nanotechnology}, Wiley, 2003.

\bibitem{Prodinger} H. Prodinger and  R. F.  Tichy, 
Fibonacci numbers of graphs,
  {\it Fibonacci Quart.} \textbf{20} (1982), 16--21. 

\bibitem{Thomassen} C. Thomassen, Tilings of the torus and the Klein
  bottle and vertex-transitive graphs on a fixed surface, {\it
    Trans. Amer. Math. Soc.} \textbf{323} (1991), 605--635.

\bibitem{Sapozhenko} A. A. Sapozhenko, 
The number of independent sets  in graphs, 
{\it Moscow Univ. Math. Bull.} \textbf{62} (2007), 116--118.  

\bibitem{Stoj} I. Stojmenovic, 
Honeycomb networks: Topological properties and communication
algorithms,  
{\it IEEE Trans. Parallel Distrib. Syst.} \textbf{8} (1997), 1036--1042.
  
\bibitem{OEIS} The On-Line Encyclopedia of Integer Sequences,
\url{http://oeis.org}.

\bibitem{Wagner} S. G.  Wagner,
The Fibonacci number of generalized Petersen graphs, 
{\it Fibonacci Quart.} \textbf{44} (2006), 362--367. 

\bibitem{Zhao} Y. Zhao,  The number of independent sets in a regular
  graph,  
{\it Combin. Probab. Comput.} \textbf{19} (2010), 315--319. 


\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B39; Secondary 05C76, 11B83, 05A15, 05C69.

\noindent \emph{Keywords: } Fibonacci number, Merrifield-Simmons
index, independent set, Zykov sum, transfer matrix method.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A003688}
\seqnum{A007070}
\seqnum{A007483}
\seqnum{A026150}
\seqnum{A028859}
\seqnum{A050402}
\seqnum{A051926}
\seqnum{A051928}
\seqnum{A078057}
\seqnum{A161941}
\seqnum{A181961}
\seqnum{A181989}
\seqnum{A182014}
\seqnum{A182019}
\seqnum{A182041}
\seqnum{A182052}
\seqnum{A182054}
\seqnum{A182077}
\seqnum{A182130}
\seqnum{A182141}
\seqnum{A182143}
 and
\seqnum{A188707}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 4 2012;
revised versions received August 22 2012; September 13 2012.
Published in {\it Journal of Integer Sequences}, September 23 2012.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in

\end{document}


</pre></body></html>