The Number of Independent Sets in a Grid Graph

DOI10.1137/S089548019528993XMaRDI QIDQ4388978zbMATH OpenOpenAlexFDO

Authors Neil J. Calkin, Herbert S. Wilf

Publication date 11 May 1998

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s089548019528993x

zbMATH Keywords

Fibonacci numberindependent setstransfer matrixgrid graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Asymptotic enumeration (05A16) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Recommendations

• scientific article; zbMATH DE number 4059411
• Enumerating independent vertex sets in grid graphs
• Counting maximal distance-independent sets in grid graphs
• Maximal independent sets on a grid graph
• On generating functions and limit theorems associated with maximal independent sets in grid graphs

Cited in

(41)

• The \(k\)-independence number of graph products
• Maximal independent sets in grid graphs
• The transfer matrices and the capacity of the 2-dimensional (1, )-runlength limited constraint
• REPETITIONS, FULLNESS, AND UNIFORMITY IN TWO-DIMENSIONAL WORDS
• The number of independent sets in an irregular graph
• Approximating the hard square entropy constant with probabilistic methods
• Asymptotic behavior of a generalized independent sets model on the two-dimensional Sierpinski gasket
• Constructing edge-disjoint Steiner paths in lexicographic product networks
• Constructing internally disjoint pendant Steiner trees in Cartesian product networks
• On the number of maximal independent sets in complete \(q\)-ary trees
• Enumerating maximal dissociation sets in three classes of grid graphs
• Nonograms: combinatorial questions and algorithms
• Excuse me! or the courteous theatregoers' problem
• Path-connectivity of lexicographic product graphs
• Merrifield-Simmons index and its entropy of the 4-8-8 lattice
• Independence complexes of \((n \times 4)\) and \((n \times 5)\)-grid graphs
• Tutte polynomials for benzenoid systems with one branched hexagon
• Extremal polyomino chains on k-matchings and k-independent sets
• Sequential cavity method for computing free energy and surface pressure
• Reconstruction of binary matrices under adjacency constraints
• Independent sets in graphs
• Upper bounds on the growth rates of independent sets in two dimensions via corner transfer matrices
• The spectrum and spanning trees of polyominos on the torus
• On generating functions and limit theorems associated with maximal independent sets in grid graphs
• The channel capacity of read/write isolated memory
• Theory of computation of multidimensional entropy with an application to the monomer-dimer problem
• A Method for Computing the Merrifield–Simmons Index on Benzenoid Systems
• Monochromatic connectivity and graph products
• scientific article; zbMATH DE number 4059411 (Why is no real title available?)
• New upper and lower bounds on the channel capacity of read/write isolated memory
• Several constants arising in statistical mechanics
• Rainbow vertex-connection and graph products
• Enumerating independent vertex sets in grid graphs
• Capacity of higher-dimensional constrained systems
• Random maximal independent sets and the unfriendly theater seating arrangement problem
• Counting maximal distance-independent sets in grid graphs
• Enumeration problems for classes of self-similar graphs
• Every grid has an independent \([1, 2]\)-set
• Planar lattice gases with nearest-neighbor exclusion
• Graphs, partitions and Fibonacci numbers
• Enumeration of matchings in complete q-ary trees

This page was built for publication: The Number of Independent Sets in a Grid Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4388978)