×

The Fibonacci number of a grid graph and a new class of integer sequences. (English) Zbl 1068.11009

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.

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

Software:

OEIS
PDFBibTeX XMLCite
Full Text: EuDML EMIS