What is and is not inside a Cayley graph?

2025/06/17 by Kolja Knauer, Knauer, Kolja, Gomez, Alvaro Soto · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.2506.14088

openalex publication_date 2025/06/17 · openalex created_date 2025/10/09 · openalex updated_date 2026/07/28

Abstract

In this note we show that there is a cubic graph of girth 5 that is not a subgraph of any minimal Cayley graph. On the other hand, we show that any Generalized Petersen Graph G(n,k) with gcd(n,k)=1 is an induced subgraph of a minimal Cayley graph. These results give insights into two comments of László Babai in [L. Babai, Automorphism groups, isomorphism, reconstruction. Graham, R. L. (ed.) et al., Handbook of combinatorics. Vol. 1-2, 1994].

Cited by

• Coloring semiminimal Cayley Graphs

Related

• Homomorphisms of binary Cayley graphs
• Two families of graphs that are Cayley on nonisomorphic groups
• On the power graphs which are Cayley graphs of some groups
• Cayley graphs on non-isomorphic groups
• Girth six cubic graphs have Petersen minors