Euler, Reinhardt The Fibonacci number of a grid graph and a new class of integer sequences. (English) Zbl 1068.11009 J. Integer Seq. 8, No. 2, Art. 05.2.6, 16 p. (2005). Let \(G\) be an \(m\times n\) grid graph with labelled vertices. Let \(i(m,n)\) denote the number of independent vertex sets in \(G\), and let \(b(m,n)\) denote the number of those indepenedent vertex sets that are maximal for set inclusion. The numbers \(i(m,n)\) are closely related to the hard-square model in statistical physics, and maximal independent sets may be associated with meta-stable liquid states of certain hard-core lattice gas models under compaction. The sequence \(b(1,n)\) is the Padovan sequence, while the sequence \(b(2,n)\) is the Fibonacci sequence. For small \(m>2\), the transfer matrix method is adapted to determine \(b(m,n)\), resulting in new integer sequences. Reviewer: László A. Székely (Columbia) Cited in 8 Documents MSC: 11B39 Fibonacci and Lucas numbers and polynomials and generalizations 11B83 Special sequences and polynomials 05A15 Exact enumeration problems, generating functions 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) Keywords:Fibonacci number; Padovan number; transfer matrix method; independent set; grid graph Software:OEIS PDFBibTeX XMLCite \textit{R. Euler}, J. Integer Seq. 8, No. 2, Art. 05.2.6, 16 p. (2005; Zbl 1068.11009) Full Text: EuDML EMIS Online Encyclopedia of Integer Sequences: Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1. Padovan sequence (or Padovan numbers): a(n) = a(n-2) + a(n-3) with a(0) = 1, a(1) = a(2) = 0. Numerators of continued fraction convergents to sqrt(2). Number of 3 X n (0,1)-matrices with no consecutive 1’s in any row or column. Number of 4 X n (0,1)-matrices with no consecutive 1’s in any row or column. Number of 5 X n matrices with entries {0,1} without adjacent 0’s in any row or column. 5th row of A089934.