Enumerating independent vertex sets in grid graphs

DOI10.1016/J.LAA.2016.08.025MaRDI QIDQ501235zbMATH OpenOpenAlexFDO

Authors Seungsang Oh, Sangyop Lee

Publication date 29 December 2016

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.00515

zbMATH Keywords

enumerationhard squareindependent vertex setMerrifield-Simmons index

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Basic linear algebra (15A99)

Abstract: A set of vertices in a graph is called independent if no two vertices of the set are connected by an edge. In this paper we use the state matrix recursion algorithm, developed by Oh, to enumerate independent vertex sets in a grid graph and even further to provide the generating function with respect to the number of vertices. We also enumerate bipartite independent vertex sets in a grid graph. The asymptotic behavior of their growth rates is presented.

Recommendations

• Maximal independent sets on a grid graph
• Maximal independent sets in grid graphs
• The Number of Independent Sets in a Grid Graph
• Algebraic independent numbers of certain types of simple graphs
• On generating functions and limit theorems associated with maximal independent sets in grid graphs

Cites work

• Energy, Hosoya index and Merrifield-Simmons index of trees with prescribed degree sequence
• Enumeration of structure-sensitive graphical subsets: Calculations
• Enumeration of structure-sensitive graphical subsets: Theory
• Graphs with maximal Hosoya index and minimal Merrifield-Simmons index
• scientific article; zbMATH DE number 4059411 (Why is no real title available?)
• scientific article; zbMATH DE number 4074878 (Why is no real title available?)
• scientific article; zbMATH DE number 3745213 (Why is no real title available?)
• Maxima and minima of the Hosoya index and the Merrifield-Simmons index
• Merrifield-Simmons index of generalized Aztec diamonds and related graphs
• Planar lattice gases with nearest-neighbor exclusion
• Quantum knots and mosaics
• Quantum knots and the number of knot mosaics
• Small knot mosaics and partition matrices
• The Hosoya index and the Merrifield-Simmons index of some graphs
• The Hosoya indices and Merrifield-Simmons indices of graphs with connectivity at most \(K^{\bigstar}\)
• The Number of Independent Sets in a Grid Graph

Cited in

(18)

• Upper bounds on the growth rates of independent sets in two dimensions via corner transfer matrices
• Domino tilings of the expanded Aztec diamond
• State matrix recursion method and monomer-dimer problem
• Number of dominating sets in cylindric square grid graphs
• Counting dissections into integral squares
• Dimer coverings of 1-slab cubic lattices
• Enumeration of 1-slab lattice links
• Maximal independent sets on a grid graph
• The Number of Independent Sets in a Grid Graph
• On generating functions and limit theorems associated with maximal independent sets in grid graphs
• Counting domineering positions
• The polynomial profile of distance games on paths and cycles
• A mathematical analysis of mosaic knitting: constraints, combinatorics, and colour-swapping symmetries
• Period and toroidal knot mosaics
• Enumeration on graph mosaics
• scientific article; zbMATH DE number 6180530 (Why is no real title available?)
• Enumerating maximal dissociation sets in three classes of grid graphs
• Quantum knot mosaics and bounds of the growth constant

This page was built for publication: Enumerating independent vertex sets in grid graphs

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