Characterization of subgroup perfect codes in Cayley graphs

被引：17
作者：
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., 1955, Theory of Groups of Finite Order, Vsecond
  • [2] Subgroups as efficient dominating sets in Cayley graphs
    Chelvam, T. Tamizh
    Mutharasu, Sivagnanam
    [J]. DISCRETE APPLIED MATHEMATICS, 2013, 161 (09) : 1187 - 1190
  • [3] Efficient dominating sets in Cayley graphs
    Dejter, IJ
    Serra, O
    [J]. DISCRETE APPLIED MATHEMATICS, 2003, 129 (2-3) : 319 - 328
  • [4] Efficient dominating sets in circulant graphs
    Deng, Yun-Ping
    Sun, Yu-Qin
    Liu, Qiong
    Wang, Hai-Chao
    [J]. DISCRETE MATHEMATICS, 2017, 340 (07) : 1503 - 1507
  • [5] Efficient dominating sets in circulant graphs with domination number prime
    Deng, Yun-Ping
    [J]. INFORMATION PROCESSING LETTERS, 2014, 114 (12) : 700 - 702
  • [6] Perfect codes in circulant graphs
    Feng, Rongquan
    Huang, He
    Zhou, Sanming
    [J]. DISCRETE MATHEMATICS, 2017, 340 (07) : 1522 - 1527
  • [7] PERFECT CODES IN CAYLEY GRAPHS
    Huang, He
    Xia, Binzhou
    Zhou, Sanming
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (01) : 548 - 559
  • [8] PERFECT CODES OVER GRAPHS
    KRATOCHVIL, J
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 40 (02) : 224 - 228
  • [9] Efficient domination in circulant graphs
    Kumar, K. Reji
    MacGillivray, Gary
    [J]. DISCRETE MATHEMATICS, 2013, 313 (06) : 767 - 771
  • [10] Independent perfect domination sets in Cayley graphs
    Lee, J
    [J]. JOURNAL OF GRAPH THEORY, 2001, 37 (04) : 213 - 219
12