Enumerating independent vertex sets in grid graphs

DOI10.1016/J.LAA.2016.08.025zbMATH Open1352.05091arXiv1609.00515OpenAlexW2962793085MaRDI QIDQ501235FDOQ501235

Authors: Seungsang Oh, Sangyop Lee 

Publication date: 29 December 2016

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

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.

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

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

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)

Cites Work

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

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 domineering positions
• Counting dissections into integral squares
• 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
• Title not available (Why is that?)
• A mathematical analysis of mosaic knitting: constraints, combinatorics, and colour-swapping symmetries
• Quantum knot mosaics and bounds of the growth constant
• Domino tilings of the expanded Aztec diamond
• Enumeration of 1-slab lattice links
• 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)