Edge pancyclic Cayley graphs on symmetric group

2025/08/18 by Cao, Mengyu, Lu, Mei, Lv, Zequn +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2508.12618

Abstract

We study the derangement graph Γ_n whose vertex set consists of all permutations of \1,…,n\, where two vertices are adjacent if and only if their corresponding permutations differ at every position. It is well-known that Γ_n is a Cayley graph, Hamiltonian and Hamilton-connected. In this paper, we prove that for n ≥ 4, the derangement graph Γ_n is edge pancyclic. Moreover, we extend this result to two broader classes of Cayley graphs defined on symmetric group.

Citations

• On triangles in derangement graphs
• All 2-transitive groups have the EKR-module property
• Solving the Ku-Wales conjecture on the eigenvalues of the derangement graph
• Eigenvalues of the Derangement Graph

Related

• Edge pancyclic derangement graphs
• On triangles in derangement graphs
• On multipartite derangement graphs
• Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)
• Cayley graph on symmetric groups with generating block transposition sets