2024/07/02 by Barber, Rachel, Dobson, Ted
#05C20 #05C60 (Secondary) #05E18 (Primary) 05C25 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2407.02316
It has long been known that a vertex-transitive graph Γ is isomorphic to a double coset graph Cos(G,H,S) of a transitive group G\leAut(Γ), a vertex stabilizer H≤ G, and some subset S⊆ G. We show that the automorphism group of the Cayley graph Cay(G,S) with connection set S can be obtained from the automorphism group of 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.