Characterization of subgroup perfect codes in Cayley graphs

被引：20

作者：

Chen, Jiyong ^{[1
]}

Wang, Yanpeng ^{[2
,3
]}

Xia, Binzhou ^{[4
]}

机构：

[1] Southern Univ Sci & Technol, Dept Math, Shenzhen 518055, Guangdong, Peoples R China

[2] Peking Univ, Sch Math Sci, Beijing 100871, Peoples R China

[3] Harbin Univ Sci & Technol, Rongcheng Campus, Harbin 150080, Heilongjiang, Peoples R China

[4] Univ Melbourne, Sch Math & Stat, Parkville, Vic 3010, Australia

来源：

DISCRETE MATHEMATICS | 2020年 / 343卷 / 05期

关键词：

Cayley graph; Perfect code; Cyclic group; Generalized quaternion group; EFFICIENT DOMINATING SETS; CIRCULANT GRAPHS;

D O I：

10.1016/j.disc.2020.111813

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A subset C of the vertex set of a graph Gamma is called a perfect code in Gamma if every vertex of Gamma is at distance no more than 1 to exactly one vertex of C. A subset C of a group G is called a perfect code of G if C is a perfect code in some Cayley graph of G. In this paper we give sufficient and necessary conditions for a subgroup H of a finite group G to be a perfect code of G. Based on this, we determine the finite groups that have no nontrivial subgroup as a perfect code, which answers a question by Ma, Walls, Wang and Zhou. (C) 2020 Elsevier B.V. All rights reserved.

引用

页数：4

共 12 条

[1]

BURNSIDE W, 1911, THEORY GROUPS FINITE

[2] Subgroups as efficient dominating sets in Cayley graphs [J].

Chelvam, T. Tamizh ;

Mutharasu, Sivagnanam .

DISCRETE APPLIED MATHEMATICS, 2013, 161 (09) :1187-1190

[3] Efficient dominating sets in Cayley graphs [J].

Dejter, IJ ;

Serra, O .

DISCRETE APPLIED MATHEMATICS, 2003, 129 (2-3) :319-328

[4] Efficient dominating sets in circulant graphs [J].

Deng, Yun-Ping ;

Sun, Yu-Qin ;

Liu, Qiong ;

Wang, Hai-Chao .

DISCRETE MATHEMATICS, 2017, 340 (07) :1503-1507

[5] Efficient dominating sets in circulant graphs with domination number prime [J].

Deng, Yun-Ping .

INFORMATION PROCESSING LETTERS, 2014, 114 (12) :700-702

[6] Perfect codes in circulant graphs [J].

Feng, Rongquan ;

Huang, He ;

Zhou, Sanming .

DISCRETE MATHEMATICS, 2017, 340 (07) :1522-1527

[7] PERFECT CODES IN CAYLEY GRAPHS [J].

Huang, He ;

Xia, Binzhou ;

Zhou, Sanming .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (01) :548-559

[8] PERFECT CODES OVER GRAPHS [J].

KRATOCHVIL, J .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 40 (02) :224-228

[9] Efficient domination in circulant graphs [J].

Kumar, K. Reji ;

MacGillivray, Gary .

DISCRETE MATHEMATICS, 2013, 313 (06) :767-771

[10] Independent perfect domination sets in Cayley graphs [J].

Lee, J .

JOURNAL OF GRAPH THEORY, 2001, 37 (04) :213-219

← 1 2 →