Asymptotic growth rate of square grids dominating sets: a symbolic dynamics approach

DOI10.1016/J.TCS.2020.03.006zbMATH Open1437.05180arXiv1906.10779OpenAlexW3014819229MaRDI QIDQ2173304FDOQ2173304

Authors: Silvère Gangloff, Alexandre Talon 

Publication date: 22 April 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: In this text, we prove the existence of an asymptotic growth rate of the number of dominating sets (and variants) on finite rectangular grids, when the dimensions of the grid grow to infinity. Moreover, we provide, for each of the variants, an algorithm which computes the growth rate. We also give bounds on these rates provided by a computer program.

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

Recommendations

• Growth rates of geometric grid classes of permutations
• scientific article; zbMATH DE number 934854
• Asymptotic results for the number of paths in a grid
• scientific article; zbMATH DE number 4008448
• Growth rates of permutation grid classes, tours on graphs, and the spectral radius
• New upper bounds on the distance domination numbers of grids
• Asymptotics for numbers of line segments and lines in a square grid
• The domination number of grids
• Upper bounds on the growth rates of hard squares and related models via corner transfer matrices
• On locating--dominating sets in infinite grids

zbMATH Keywords

entropysymbolic dynamicsdominating setscomputabilitysubshifts of finite type

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Symbolic dynamics (37B10)

Cites Work

• An Introduction to Symbolic Dynamics and Coding
• The domination number of grids
• Neighborhood and domination polynomials of graphs
• Entropies realizable by block gluing \(\mathbb{Z}^{d}\) shifts of finite type
• The 2-domination and Roman domination numbers of grid graphs

Cited In (2)

• Staircases, dominoes, and the growth rate of 1324-avoiders
• Number of dominating sets in cylindric square grid graphs

This page was built for publication: Asymptotic growth rate of square grids dominating sets: a symbolic dynamics approach

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