Geodesic
The Fibonacci number of a grid graph and a new class of integer sequences
Journal of integer sequences, Tome 8 (2005) no. 2.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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.
Classification : 11B39, 11B83, 05A15, 05C69
Keywords: Fibonacci number, Padovan number, transfer matrix method, independent set, grid graph 
@article{JIS_2005__8_2_a5,
     author = {Euler, Reinhardt},
     title = {The {Fibonacci} number of a grid graph and a new class of integer sequences},
     journal = {Journal of integer sequences},
     publisher = {mathdoc},
     volume = {8},
     number = {2},
     year = {2005},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JIS_2005__8_2_a5/}
}
TY  - JOUR
AU  - Euler, Reinhardt
TI  - The Fibonacci number of a grid graph and a new class of integer sequences
JO  - Journal of integer sequences
PY  - 2005
VL  - 8
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JIS_2005__8_2_a5/
LA  - en
ID  - JIS_2005__8_2_a5
ER  - 
%0 Journal Article
%A Euler, Reinhardt
%T The Fibonacci number of a grid graph and a new class of integer sequences
%J Journal of integer sequences
%D 2005
%V 8
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JIS_2005__8_2_a5/
%G en
%F JIS_2005__8_2_a5
Euler, Reinhardt. The Fibonacci number of a grid graph and a new class of integer sequences. Journal of integer sequences, Tome 8 (2005) no. 2. http://geodesic.mathdoc.fr/item/JIS_2005__8_2_a5/