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 条
  • [21] Disconnected character graphs and odd dominating sets
    Ebrahimi, Mahdi
    COMMUNICATIONS IN ALGEBRA, 2021, 49 (08) : 3310 - 3314
  • [22] On dominating sets of maximal outerplanar and planar graphs
    Li, Zepeng
    Zhu, Enqiang
    Shao, Zehui
    Xu, Jin
    DISCRETE APPLIED MATHEMATICS, 2016, 198 : 164 - 169
  • [23] Metric-locating-dominating sets in graphs
    Henning, MA
    Oellermann, OR
    ARS COMBINATORIA, 2004, 73 : 129 - 141
  • [24] Cactus graphs with unique minimum dominating sets
    Fischermann, M
    Volkmann, L
    UTILITAS MATHEMATICA, 2003, 63 : 229 - 238
  • [25] On the number of independent and k-dominating sets in graphs with average vertex degree at most k
    Taletskii, D. S.
    SBORNIK MATHEMATICS, 2023, 214 (11) : 1627 - 1650
  • [26] Dominating sets with small clique covering number
    Penrice, SG
    JOURNAL OF GRAPH THEORY, 1997, 25 (02) : 101 - 105
  • [27] Counting the number of dominating sets of cactus chains
    Alikhani, S.
    Jahari, S.
    Mehryar, M.
    Hasni, R.
    OPTOELECTRONICS AND ADVANCED MATERIALS-RAPID COMMUNICATIONS, 2014, 8 (9-10): : 955 - 960
  • [28] Split domination number of divisible dominating graphs
    Amutha, S.
    Prabha, K. Suriya
    Anbazhagan, N.
    Shanthi, P.
    JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2021, 24 (04): : 997 - 1006
  • [29] An explicit construction of optimal dominating and [1,2]-dominating sets in grid
    Sharifani, P.
    Hooshmandasl, M. R.
    Meybodi, M. Alambardar
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2020, 17 (03) : 870 - 876
  • [30] On proper (1,2)-dominating sets in graphs
    Michalski, Adrian
    Wloch, Iwona
    Dettlaff, Magda
    Lemanska, Magdalena
    MATHEMATICAL METHODS IN THE APPLIED SCIENCES, 2022, 45 (11) : 7050 - 7057
12345