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 条
  • [31] Disjoint Paired-Dominating sets in Cubic Graphs
    Bacso, Gabor
    Bujtas, Csilla
    Tompkins, Casey
    Tuza, Zsolt
    GRAPHS AND COMBINATORICS, 2019, 35 (05) : 1129 - 1138
  • [32] Dominating Sets and Induced Matchings in Orthogonal Ray Graphs
    Takaoka, Asahi
    Tayu, Satoshi
    Ueno, Shuichi
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2014, E97D (12): : 3101 - 3109
  • [33] DOMINATING SETS OF SOME GRAPHS ASSOCIATED TO COMMUTATIVE RINGS
    Mojdeh, D. A.
    Rahimi, A. M.
    COMMUNICATIONS IN ALGEBRA, 2012, 40 (09) : 3389 - 3396
  • [34] ON MINIMUM INTERSECTIONS OF CERTAIN SECONDARY DOMINATING SETS IN GRAPHS
    Kosiorowska, Anna
    Michalski, Adrian
    Wloch, Iwona
    OPUSCULA MATHEMATICA, 2023, 43 (06) : 813 - 827
  • [35] Disjoint Paired-Dominating sets in Cubic Graphs
    Gábor Bacsó
    Csilla Bujtás
    Casey Tompkins
    Zsolt Tuza
    Graphs and Combinatorics, 2019, 35 : 1129 - 1138
  • [36] Tropical dominating sets in vertex-coloured graphs
    d'Auriac, J. -A. Angles
    Bujtas, Cs.
    El Maftouhi, A.
    Karpinski, M.
    Manoussakis, Y.
    Montero, L.
    Narayanan, N.
    Rosaz, L.
    Thapper, J.
    Tuza, Zs.
    JOURNAL OF DISCRETE ALGORITHMS, 2018, 48 (27-41) : 27 - 41
  • [37] Dominating Sets in Two-Directional Orthogonal Ray Graphs
    Takaoka, Asahi
    Tayu, Satoshi
    Ueno, Shuichi
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2015, E98D (08): : 1592 - 1595
  • [38] Locating and differentiating-total dominating sets in unicyclic graphs
    Ning, Wenjie
    Lu, Mei
    Guo, Jia
    ARS COMBINATORIA, 2017, 132 : 241 - 255
  • [39] Explicit construction of mixed dominating sets in generalized Petersen graphs
    Olyaei, Meysam Rajaati Bavil
    Meybodi, Mohsen Alambardar
    Hooshmandasl, Mohammad Reza
    Shakiba, Ali
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2024, 48 (04)
  • [40] Local algorithms for dominating and connected dominating sets of unit disk graphs with location aware nodes
    Czyzowicz, J.
    Dobrev, S.
    Fevens, T.
    Gonzalez-Aguilar, H.
    Kranakis, E.
    Opatrny, J.
    Urrutia, J.
    LATIN 2008: THEORETICAL INFORMATICS, 2008, 4957 : 158 - +
12345