|Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.6|
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.