Perfect codes in Cayley graphs

DOI10.1137/17M1129532MaRDI QIDQ4604646zbMATHFDO

Authors He Huang, Binzhou Xia, Sanming Zhou

Publication date 5 March 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.03755

zbMATH Keywords

Cayley graphtilingefficient dominating setperfect code

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Combinatorial codes (94B25)

Abstract: Given a graph $Gamma$, a subset $C$ of $V(Gamma)$ is called a perfect code in $Gamma$ if every vertex of $Gamma$ is at distance no more than one to exactly one vertex in $C$, and a subset $C$ of $V(Gamma)$ is called a total perfect code in $Gamma$ if every vertex of $Gamma$ is adjacent to exactly one vertex in $C$. In this paper we study perfect codes and total perfect codes in Cayley graphs, with a focus on the following themes: when a subgroup of a given group is a (total) perfect code in a Cayley graph of the group; and how to construct new (total) perfect codes in a Cayley graph from known ones using automorphisms of the underlying group. We prove several results around these questions.

Recommendations

• Total perfect codes in Cayley graphs
• Characterization of subgroup perfect codes in Cayley graphs
• Perfect codes in Cayley sum graphs
• On subgroup perfect codes in Cayley graphs
• Perfect codes in vertex-transitive graphs

Cites work

• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 3013344 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• A survey of perfect codes
• A survey of perfect codes
• Codes and anticodes in the Grassman graph
• Efficient dominating sets in Cayley graphs.
• Efficient dominating sets in circulant graphs
• Efficient dominating sets in circulant graphs with domination number prime
• Efficient domination in circulant graphs
• Efficient domination in circulant graphs with two chord lengths
• Factoring Finite Abelian Groups by Subsets with Maximal Span
• Factoring groups into subsets.
• Full Rank Tilings of Finite Abelian Groups
• Independent perfect domination sets in Cayley graphs
• On perfect codes in the Hamming schemes H(n,q) with q arbitrary
• On the norm of a group
• Perfect Codes From Cayley Graphs Over Lipschitz Integers
• Perfect Codes for Metrics Induced by Circulant Graphs
• Perfect codes and regular partitions in graphs and groups
• Perfect codes in \(\mathrm{SL}(2,2^f)\)
• Perfect codes in circulant graphs
• Perfect codes in graphs
• Perfect codes in the graphs O_k and L(O_k)
• Perfect codes in the graphs \(O_k\)
• Perfect codes over graphs
• Power automorphisms of a group
• Quotients of Gaussian graphs and their application to perfect codes
• Subgroups as efficient dominating sets in Cayley graphs
• Total perfect codes in Cayley graphs

Cited in

(38)

• Regular sets in Cayley sum graphs
• Cyclotomic graphs and perfect codes
• On subgroup regular sets in Cayley sum graphs
• Characterizing subgroup perfect codes by 2-subgroups
• Classification of efficient dominating sets of circulant graphs of degree 5
• Perfect codes in \(m\)-Cayley hypergraphs
• Regular sets in circulant graphs with degree 3
• Subgroup perfect codes in Cayley sum graphs
• An infinite class of Neumaier graphs and non-existence results
• Perfect codes in vertex-transitive graphs
• On non-normal subgroup perfect codes
• Perfect codes in circulant graphs
• Neighbour-transitive codes in Kneser graphs
• Perfect codes in 2-valent Cayley digraphs on abelian groups
• On regular sets in Cayley graphs
• Subgroup total perfect codes in Cayley sum graphs
• Regular sets in Cayley graphs
• On codes in the projective linear group \(\mathrm{PGL}(2,q)\)
• On connected components and perfect codes of proper order graphs of finite groups
• scientific article; zbMATH DE number 14398 (Why is no real title available?)
• Perfect codes in Cayley sum graphs
• Perfect Codes From Cayley Graphs Over Lipschitz Integers
• On the subgroup perfect codes in Cayley graphs
• Subgroup Perfect Codes in Cayley Graphs
• Parameterized complexity of minimum membership dominating set
• Corrigendum to: ``On subgroup perfect codes in Cayley graphs
• Perfect \(t\)-codes in Cayley graphs of groups
• Total perfect codes in Cayley graphs
• Some codes in symmetric and linear groups
• Perfect codes in proper reduced power graphs of finite groups
• On subgroup perfect codes in Cayley graphs
• Characterization of subgroup perfect codes in Cayley graphs
• Subset Perfect Codes of Finite Commutative Rings Over Induced Subgraphs of Unit Graphs
• On subgroup perfect codes in Cayley sum graphs
• Perfect codes in commuting graphs of symmetric groups
• Subgroup regular sets in Cayley graphs
• A NOTE ON REGULAR SETS IN CAYLEY GRAPHS
• Perfect codes from \(\operatorname{PGL}(2,5)\) in star graphs

This page was built for publication: Perfect codes in Cayley graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604646)