Perfect codes in vertex-transitive graphs

DOI10.1016/J.JCTA.2023.105737MaRDI QIDQ6385422arXivFDO

Authors Yu-Ting Wang, Jun-Yang Zhang

Publication date 12 December 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.JCTA.2023.105737

Mathematics Subject Classification ID

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

arXiv classification

math.CO

Abstract: Given a graph $Gamma$, a perfect code in $Gamma$ is an independent set $C$ of vertices of $Gamma$ such that every vertex outside of $C$ is adjacent to a unique vertex in $C$, and a total perfect code in $Gamma$ is a set $C$ of vertices of $Gamma$ such that every vertex of $Gamma$ is adjacent to a unique vertex in $C$. To study (total) perfect codes in vertex-transitive graphs, we generalize the concept of subgroup (total) perfect code of a finite group introduced in cite{HXZ18} as follows: Given a finite group $G$ and a subgroup $H$ of $G$, a subgroup $A$ of $G$ containing $H$ is called a subgroup (total) perfect code of the pair $(G,H)$ if there exists a coset graph $Cos(G,H,U)$ such that the set consisting of left cosets of $H$ in $A$ is a (total) perfect code in $Cos(G,H,U)$. We give a necessary and sufficient condition for a subgroup $A$ of $G$ containing $H$ to be a (total) perfect code of the pair $(G,H)$ and generalize a few known results of subgroup (total) perfect codes of groups. We also construct some examples of subgroup perfect codes of the pair $(G,H)$ and propose a few problems for further research.

This page was built for publication: Perfect codes in vertex-transitive graphs

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