Number of Dominating Sets in Cylindric Square Grid Graphs

被引：5

作者：

Oh, Seungsang ^{[1
]}

机构：

[1] Korea Univ, Dept Math, Seoul 02841, South Korea

来源：

GRAPHS AND COMBINATORICS | 2021年 / 37卷 / 04期

关键词：

Domination polynomial; Dominating set; Cylindric square grid;

D O I：

10.1007/s00373-021-02323-8

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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

页数：16

共 18 条

[1]

Alanko S, 2011, ELECTRON J COMB, V18

[2]

Alikhani S, 2014, ARS COMBINATORIA, V114, P257

[3]

CHANG TY, 1994, ARS COMBINATORIA, V38, P97

[4] THE DOMINATION NUMBERS OF THE 5XN AND 6XN GRID GRAPHS [J].

CHANG, TY ;

CLARK, WE .

JOURNAL OF GRAPH THEORY, 1993, 17 (01) :81-107

[5]

Chérifi R, 2001, ARS COMBINATORIA, V60, P307

[6]

Cockayne E.J., 1985, CONGR NUMER CONF J N, V47, P217

[7] THE DOMINATION NUMBER OF GRIDS [J].

Goncalves, Daniel ;

Pinlou, Alexandre ;

Rao, Michael ;

Thomasse, Stephan .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2011, 25 (03) :1443-1453

[8]

Guichard D. R., 2004, Journal of Combinatorial Mathematics and Combinatorial Computing, V49, P215

[9]

Haynes T.W., 2013, Fundamentals of Domination in Graphs

[10]

Hedetniemi S.T., 1991, Topics on domination

← 1 2 →