Number of Dominating Sets in Cylindric Square Grid Graphs

被引：0
|
作者：
Seungsang Oh
机构：
[1] Korea University,Department of Mathematics
来源：
Graphs and Combinatorics | 2021年 / 37卷
关键词：
Domination polynomial; Dominating set; Cylindric square grid; 05A15; 05C69;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：1357 / 1372
页数：15
相关论文
共 50 条
  • [41] Partitioning Claw-Free Subcubic Graphs into Two Dominating Sets
    Cui, Qing
    GRAPHS AND COMBINATORICS, 2020, 36 (06) : 1723 - 1740
  • [42] Partitioning Claw-Free Subcubic Graphs into Two Dominating Sets
    Qing Cui
    Graphs and Combinatorics, 2020, 36 : 1723 - 1740
  • [43] Finding Hidden Hubs and Dominating Sets in Sparse Graphs by Randomized Neighborhood Queries
    Damaschke, Peter
    NETWORKS, 2011, 57 (04) : 344 - 350
  • [44] Metric-locating-dominating sets of graphs for constructing related subsets of vertices
    Gonzalez, Antonio
    Hernando, Carmen
    Mora, Merce
    APPLIED MATHEMATICS AND COMPUTATION, 2018, 332 : 449 - 456
  • [45] The average order of dominating sets of a graph
    Beaton, Iain
    Brown, Jason I.
    DISCRETE MATHEMATICS, 2021, 344 (12)
  • [46] Global secure sets of grid-like graphs
    Ho, Yiu Yu
    Dutton, Ronald
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (06) : 490 - 496
  • [47] Reconfiguration of dominating sets
    Suzuki, Akira
    Mouawad, Amer E.
    Nishimura, Naomi
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 32 (04) : 1182 - 1195
  • [48] On the Structure of Dominating Graphs
    Saeid Alikhani
    Davood Fatehi
    Sandi Klavžar
    Graphs and Combinatorics, 2017, 33 : 665 - 672
  • [49] Dominating sets of centipedes
    Alikhani, Saeid
    Peng, Yee-Hock
    JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2009, 12 (04): : 411 - 428
  • [50] Reconfiguration of dominating sets
    Akira Suzuki
    Amer E. Mouawad
    Naomi Nishimura
    Journal of Combinatorial Optimization, 2016, 32 : 1182 - 1195
12345