Total perfect codes in Cayley graphs

被引：31
作者：
Zhou, Sanming [1 ]
机构：
[1] Univ Melbourne, Sch Math & Stat, Parkville, Vic 3010, Australia
来源：
DESIGNS CODES AND CRYPTOGRAPHY | 2016年 / 81卷 / 03期
基金：
澳大利亚研究理事会;
关键词：
Perfect code; Total perfect code; Efficient dominating set; Efficient open dominating set; Total perfect dominating set; Cayley graph; EFFICIENT DOMINATION; SETS;
D O I：
10.1007/s10623-015-0169-0
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
A total perfect code in a graph Gamma is a subset C of V(Gamma) such that every vertex of Gamma is adjacent to exactly one vertex in C. We give necessary and sufficient conditions for a conjugation-closed subset of a group to be a total perfect code in a Cayley graph of the group. As an application we show that a Cayley graph on an elementary abelian 2-group admits a total perfect code if and only if its degree is a power of 2. We also obtain necessary conditions for a Cayley graph of a group with connection set closed under conjugation to admit a total perfect code.
引用
收藏
页码：489 / 504
页数：16
相关论文
共 42 条
  • [1] Abay-Asmerom G, 2008, ARS COMBINATORIA, V88, P129
  • [2] On perfect codes and related concepts
    Ahlswede, R
    Aydinian, HK
    Khachatrian, LH
    [J]. DESIGNS CODES AND CRYPTOGRAPHY, 2001, 22 (03) : 221 - 237
  • [3] LATTICE-LIKE TOTAL PERFECT CODES
    Araujo, Carlos
    Dejter, Italo
    [J]. DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2014, 34 (01) : 57 - 74
  • [4] PERFECT CODES IN HAMMING SCHEMES H(N,Q) WITH Q ARBITRARY
    BANNAI, E
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1977, 23 (01) : 52 - 67
  • [5] Biggs N., 1973, Journal of Combinatorial Theory, Series B, V15, P289, DOI 10.1016/0095-8956(73)90042-7
  • [6] Odd neighborhood transversals on grid graphs
    Cowen, Robert
    Hechler, Stephen H.
    Kennedy, John W.
    Steinberg, Arthur
    [J]. DISCRETE MATHEMATICS, 2007, 307 (17-18) : 2200 - 2208
  • [7] Efficient dominating sets in Cayley graphs
    Dejter, IJ
    Serra, O
    [J]. DISCRETE APPLIED MATHEMATICS, 2003, 129 (2-3) : 319 - 328
  • [8] Dejter IJ, 2008, AUSTRALAS J COMB, V42, P99
  • [9] DELSARTE P, 1973, PHILIPS RES REP, P1
  • [10] PERFECT CODES AND REGULAR PARTITIONS IN GRAPHS AND GROUPS
    ETIENNE, G
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 1987, 8 (02) : 139 - 144
12345