Domination in the generalized Petersen graph P(ck, k)

被引:0
作者
Zhao, Weiliang [1 ]
Zheng, Meifang [1 ]
Wu, Lirong [1 ]
机构
[1] Zhejiang Ind Polytech Coll, Shaoxing 312000, Peoples R China
关键词
Domination number; The generalized Petersen graph; NUMBER;
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let G = (V, E) be a graph. A subset S C V is a dominating set of G, if every vertex u is an element of V - S is dominated by some vertex v is an element of S. The domination number, denoted by gamma(G), is the minimum cardinality of a dominating set. Determining the domination number of a graph G is an NP-complete problem, and only for few families of graphs, the exact domination number is known. In this paper, we study the domination number for the generalized Petersen graph P(ck, k), where c >= 3 is a constant. We obtain upper bound on gamma(P(ck, k)) for general c. We also show that gamma(P(3k,k)) =[-5k/3] for any k >= 1, and gamma(P(4k, k)) = 2k for odd k.
引用
收藏
页码:157 / 163
页数:7
相关论文
共 50 条
[41]   Private domination number of a graph [J].
Prasad, B. Jaya ;
Chelvam, T. Tamizh ;
Chellathurai, S. Robinson .
JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2007, 10 (05) :661-666
[42]   Graph products and integer domination [J].
John, Niluk ;
Suen, Stephen .
DISCRETE MATHEMATICS, 2013, 313 (03) :217-224
[43]   Domination in Discrete Topology Graph [J].
Jabor, Ali Ameer ;
Omran, Ahmed Abd-Ali .
THIRD INTERNATIONAL CONFERENCE OF MATHEMATICAL SCIENCES (ICMS 2019), 2019, 2183
[44]   The nonsplit domination number of a graph [J].
Kulli, VR ;
Janakiram, B .
INDIAN JOURNAL OF PURE & APPLIED MATHEMATICS, 2000, 31 (04) :441-447
[45]   The Domination Number of a Random Graph [J].
Henning, Michael A. ;
Yeo, Anders .
UTILITAS MATHEMATICA, 2014, 94 :315-328
[46]   Domination in transformation graph G(-+-) [J].
Jebitha, M. K. Angel ;
Joseph, J. Paulraj .
JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2011, 14 (03) :279-303
[47]   Total Domination Polynomial of A Graph [J].
Chaluvaraju, B. ;
Chaitra, V. .
JOURNAL OF INFORMATICS AND MATHEMATICAL SCIENCES, 2014, 6 (02) :87-92
[48]   TOTAL DOMINATION IN GENERALIZED PRISMS AND A NEW DOMINATION INVARIANT [J].
Tepeh, Aleksandra .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2021, 41 (04) :1165-1178
[49]   On the domination and signed domination numbers of zero-divisor graph [J].
Vatandoost, Ebrahim ;
Ramezani, Fatemeh .
ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2016, 4 (02) :148-156
[50]   Petersen Graph is Uniformly Most-Reliable [J].
Rela, Guillermo ;
Robledo, Franco ;
Romero, Pablo .
MACHINE LEARNING, OPTIMIZATION, AND BIG DATA, MOD 2017, 2018, 10710 :426-435