Finding automorphism groups of double coset graphs and Cayley graphs are equivalent
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910510152155136 |
|---|---|
| author | Barber, Rachel Dobson, Ted |
| author_facet | Barber, Rachel Dobson, Ted |
| contents | It has long been known that a vertex-transitive graph $Γ$ is isomorphic to a double coset graph $\text{Cos}(G,H,S)$ of a transitive group $G\le\text{Aut}(Γ)$, a vertex stabilizer $H\le G$, and some subset $S\subseteq G$. We show that the automorphism group of the Cayley graph $\text{Cay}(G,S)$ with connection set $S$ can be obtained from the automorphism group of $\text{Cos}(G,H,S)$ and vice versa. We also show that the isomorphism problem for double coset graphs is equivalent to the isomorphism problem for Cayley graphs provided one knows all groups $G$ for which a fixed Cayley graph is a Cayley graph of $G$. Our main tool is a "recognition theorem", which recognizes when a Cayley graph of a group $G$ is a wreath product of two graphs based upon its connection set. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_02316 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Finding automorphism groups of double coset graphs and Cayley graphs are equivalent Barber, Rachel Dobson, Ted Combinatorics 05E18 (Primary) 05C25, 05C20, 05C60 (Secondary) It has long been known that a vertex-transitive graph $Γ$ is isomorphic to a double coset graph $\text{Cos}(G,H,S)$ of a transitive group $G\le\text{Aut}(Γ)$, a vertex stabilizer $H\le G$, and some subset $S\subseteq G$. We show that the automorphism group of the Cayley graph $\text{Cay}(G,S)$ with connection set $S$ can be obtained from the automorphism group of $\text{Cos}(G,H,S)$ and vice versa. We also show that the isomorphism problem for double coset graphs is equivalent to the isomorphism problem for Cayley graphs provided one knows all groups $G$ for which a fixed Cayley graph is a Cayley graph of $G$. Our main tool is a "recognition theorem", which recognizes when a Cayley graph of a group $G$ is a wreath product of two graphs based upon its connection set. |
| title | Finding automorphism groups of double coset graphs and Cayley graphs are equivalent |
| topic | Combinatorics 05E18 (Primary) 05C25, 05C20, 05C60 (Secondary) |
| url | https://arxiv.org/abs/2407.02316 |