TY - JOUR
T1 - Number of Dominating Sets in Cylindric Square Grid Graphs
AU - Oh, Seungsang
N1 - Funding Information:
This work was supported by Institute for Information and communications Technology Planning and Evaluation (IITP) grant funded by the Korea government(MSIT) (No. 2019-0-00033, Study on Quantum Security Evaluation of Cryptography based on Computational Quantum Complexity).
Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature.
PY - 2021/7
Y1 - 2021/7
N2 - A dominating set of a graph is a subset D of the vertices such that every vertex not in D is adjacent to some vertex of D. In this paper, we introduce several variants of dominating sets in the square grid, periodic square grid and cylindric square grid by considering translation symmetry. We provide their exact enumerations in terms of domination polynomials. We also analyze the asymptotic behavior of the growth rates of their cardinality.
AB - A dominating set of a graph is a subset D of the vertices such that every vertex not in D is adjacent to some vertex of D. In this paper, we introduce several variants of dominating sets in the square grid, periodic square grid and cylindric square grid by considering translation symmetry. We provide their exact enumerations in terms of domination polynomials. We also analyze the asymptotic behavior of the growth rates of their cardinality.
KW - Cylindric square grid
KW - Dominating set
KW - Domination polynomial
UR - http://www.scopus.com/inward/record.url?scp=85105115585&partnerID=8YFLogxK
U2 - 10.1007/s00373-021-02323-8
DO - 10.1007/s00373-021-02323-8
M3 - Article
AN - SCOPUS:85105115585
SN - 0911-0119
VL - 37
SP - 1357
EP - 1372
JO - Graphs and Combinatorics
JF - Graphs and Combinatorics
IS - 4
ER -