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.

11B39, 11B83, 05A15, 05C69

Fibonacci number, Padovan number, transfer matrix method, independent set, grid graph