Perfect codes and regular sets in vertex-transitive graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915693480378368 |
|---|---|
| author | Abdollahi, Alireza Akhlaghi, Zeinab Arezoomand, Majid |
| author_facet | Abdollahi, Alireza Akhlaghi, Zeinab Arezoomand, Majid |
| contents | A subset \( C \) of the vertex set \( V \) of a graph \( Γ= (V,E) \) is termed an $(r,s)$-regular set if each vertex in \( C \) is adjacent to exactly \( r \) other vertices in \( C \), while each vertex not in \( C \) is adjacent to precisely \( s \) vertices in \( C \). A specific case, known as a $(0,1)$-regular set, is referred to as a perfect code. In this paper, we will delve into $(r,s)$-regular sets in the context of vertex-transitive graphs. It is noteworthy that any vertex-transitive graph can be represented as a coset graph \( \Cos(G,H,U) \). When examining a group \( G \) and a subgroup \( H \) of \( G \), a subgroup \( A \) that encompasses \( H \) is identified as an $(r,s)$-regular set related to the pair \( (G,H) \) if there exists a coset graph \( \Cos(G,H,U) \) such that the set of left cosets of \( H \) in \( A \) forms an $(r,s)$-regular set within this graph. In this paper, we present both a necessary and sufficient condition for determining when a normal subgroup \( A \) that includes \( H \) as a normal subgroup qualifies as an $(r,s)$-regular set for the pair \( (G,H) \). Furthermore, if \( A \) is a normal subgroup of \( G \) containing \( H \), we establish a relationship between \( A \) being a perfect code of \( (G,H) \) and the quotient \( N_A(H)/H \) being a perfect code of \(( N_G(H)/H, {1_{N_{G}(H)/H}}) \). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_21242 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Perfect codes and regular sets in vertex-transitive graphs Abdollahi, Alireza Akhlaghi, Zeinab Arezoomand, Majid Combinatorics 05C25, 05C69, 94B25 A subset \( C \) of the vertex set \( V \) of a graph \( Γ= (V,E) \) is termed an $(r,s)$-regular set if each vertex in \( C \) is adjacent to exactly \( r \) other vertices in \( C \), while each vertex not in \( C \) is adjacent to precisely \( s \) vertices in \( C \). A specific case, known as a $(0,1)$-regular set, is referred to as a perfect code. In this paper, we will delve into $(r,s)$-regular sets in the context of vertex-transitive graphs. It is noteworthy that any vertex-transitive graph can be represented as a coset graph \( \Cos(G,H,U) \). When examining a group \( G \) and a subgroup \( H \) of \( G \), a subgroup \( A \) that encompasses \( H \) is identified as an $(r,s)$-regular set related to the pair \( (G,H) \) if there exists a coset graph \( \Cos(G,H,U) \) such that the set of left cosets of \( H \) in \( A \) forms an $(r,s)$-regular set within this graph. In this paper, we present both a necessary and sufficient condition for determining when a normal subgroup \( A \) that includes \( H \) as a normal subgroup qualifies as an $(r,s)$-regular set for the pair \( (G,H) \). Furthermore, if \( A \) is a normal subgroup of \( G \) containing \( H \), we establish a relationship between \( A \) being a perfect code of \( (G,H) \) and the quotient \( N_A(H)/H \) being a perfect code of \(( N_G(H)/H, {1_{N_{G}(H)/H}}) \). |
| title | Perfect codes and regular sets in vertex-transitive graphs |
| topic | Combinatorics 05C25, 05C69, 94B25 |
| url | https://arxiv.org/abs/2512.21242 |