Number of Dominating Sets in Cylindric Square Grid Graphs

Seungsang Oh

doi:10.1007/s00373-021-02323-8

Number of Dominating Sets in Cylindric Square Grid Graphs

Seungsang Oh

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	1357-1372
Number of pages	16
Journal	Graphs and Combinatorics
Volume	37
Issue number	4
DOIs	https://doi.org/10.1007/s00373-021-02323-8
Publication status	Published - 2021 Jul

Bibliographical note

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.

Keywords

Cylindric square grid
Dominating set
Domination polynomial

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-021-02323-8

Cite this

@article{c59325f082ba460cb9c9e1c76b3a1c6d,

title = "Number of Dominating Sets in Cylindric Square Grid Graphs",

abstract = "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.",

keywords = "Cylindric square grid, Dominating set, Domination polynomial",

author = "Seungsang Oh",

note = "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: {\textcopyright} 2021, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature.",

year = "2021",

month = jul,

doi = "10.1007/s00373-021-02323-8",

language = "English",

volume = "37",

pages = "1357--1372",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "4",

}

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 -

Number of Dominating Sets in Cylindric Square Grid Graphs

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this