Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.6

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 .)

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