On subgroup perfect codes in vertex-transitive graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910783918571520 |
|---|---|
| author | Xia, Binzhou Zhang, Junyang Zhang, Zhishuo |
| author_facet | Xia, Binzhou Zhang, Junyang Zhang, Zhishuo |
| contents | A subset $C$ of the vertex set $V$ of a graph $Γ$ is called a perfect code in $Γ$ if every vertex in $V\setminus C$ is adjacent to exactly one vertex in $C$. Given a group $G$ and a subgroup $H$ of $G$, a subgroup $A$ of $G$ containing $H$ is called a perfect code of the pair $(G,H)$ if there exists a coset graph $\mathrm{Cos}(G,H,U)$ such that the set of left cosets of $H$ in $A$ is a perfect code in $\mathrm{Cos}(G,H,U)$. In particular, $A$ is called a perfect code of $G$ if $A$ is a perfect code of the pair $(G,1)$. In this paper, we give a characterization of $A$ to be a perfect code of the pair $(G,H)$ under the assumption that $H$ is a perfect code of $G$. As a corollary, we derive an additional sufficient and necessary condition for $A$ to be a perfect code of $G$. Moreover, we establish conditions under which $A$ is not a perfect code of $(G,H)$, which is applied to construct infinitely many counterexamples to a question posed by Wang and Zhang [\emph{J.~Combin.~Theory~Ser.~A}, 196 (2023) 105737]. Furthermore, we initiate the study of determining which maximal subgroups of $S_n$ are perfect codes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_08101 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On subgroup perfect codes in vertex-transitive graphs Xia, Binzhou Zhang, Junyang Zhang, Zhishuo Combinatorics A subset $C$ of the vertex set $V$ of a graph $Γ$ is called a perfect code in $Γ$ if every vertex in $V\setminus C$ is adjacent to exactly one vertex in $C$. Given a group $G$ and a subgroup $H$ of $G$, a subgroup $A$ of $G$ containing $H$ is called a perfect code of the pair $(G,H)$ if there exists a coset graph $\mathrm{Cos}(G,H,U)$ such that the set of left cosets of $H$ in $A$ is a perfect code in $\mathrm{Cos}(G,H,U)$. In particular, $A$ is called a perfect code of $G$ if $A$ is a perfect code of the pair $(G,1)$. In this paper, we give a characterization of $A$ to be a perfect code of the pair $(G,H)$ under the assumption that $H$ is a perfect code of $G$. As a corollary, we derive an additional sufficient and necessary condition for $A$ to be a perfect code of $G$. Moreover, we establish conditions under which $A$ is not a perfect code of $(G,H)$, which is applied to construct infinitely many counterexamples to a question posed by Wang and Zhang [\emph{J.~Combin.~Theory~Ser.~A}, 196 (2023) 105737]. Furthermore, we initiate the study of determining which maximal subgroups of $S_n$ are perfect codes. |
| title | On subgroup perfect codes in vertex-transitive graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2501.08101 |