Perfect Codes in Cayley Graphs
Perfect Codes in Cayley Graphs
复制标题
DOI：
10.1137/17m1129532
复制
发表时间：
2016-09
期刊：
影响因子：
--
通讯作者：
He Huang;Binzhou Xia;Sanming Zhou
中科院分区：
文献类型：
--
作者：
He Huang;Binzhou Xia;Sanming Zhou
给定一个图$\Gamma$，$V（\Gamma）$的子集$C$称为$\Gamma$中的完美码，如果$\Gamma$的每个顶点到$C$中的恰好一个顶点的距离不超过1，并且$V（\Gamma）$的子集$C$称为$\Gamma$中的全完美码，如果$\Gamma$的每个顶点都与$C$中的恰好一个顶点相邻。本文主要研究Cayley图中的完全码和全完全码，重点讨论了以下问题：给定群的子群在Cayley图中何时是（全）完全码;以及如何利用基群的自同构从已知的Cayley图构造新的（全）完全码.我们证明了围绕这些问题的几个结果。
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.