##
**
The Fibonacci Number of a Grid Graph and a New Class of Integer Sequences
**

###
Reinhardt Euler

Faculté des Sciences

B.P. 809

20 Avenue Le Gorgeu

29285 Brest Cedex

France

**Abstract:**
Given a grid graph *G* of size *mn*,
we study the number *i(m,n)* of
independent sets in *G*, as well as *b(m,n)*,
the number of maximal such
sets. It turns out that the initial cases *b(1,n)* and *b(2,n)*
lead to
a Padovan and a Fibonacci sequence.
To determine *b(m,n)* for *m > 2*
we
present an adaptation of the transfer matrix method, well known for
calculating *i(m,n)*. Finally, we apply our method to obtain explicit
values of *b(m,n)* for *m=3,4,5* and provide the corresponding
generating functions.

(Concerned with sequences
A000045
A000931
A001333
A051736
A051737 and
A089936
.)

**
Full version: pdf,
dvi,
ps,
latex
**

Received October 7 2004;
revised version received February 7 2005; April 12 2005.
Published in *Journal of Integer Sequences* May 17 2005.

Return to
**Journal of Integer Sequences home page**