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

enumerationMerrifield-Simmons indexhard squareindependent vertex set

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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

(17)

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

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)