Cayley graphs formed by conjugate generating sets of S_n

2007/11/20 by Steinhardt, Jacob
#05C25 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.0711.3057

Abstract

We investigate subsets of the symmetric group with structure similar to that of a graph. The trees of these subsets correspond to minimal conjugate generating sets of the symmetric group. There are two main theorems in this paper. The first is a characterization of minimal conjugate generating sets of S_n. The second is a generalization of a result due to Feng characterizing the automorphism groups of the Cayley graphs formed by certain generating sets composed of cycles. We compute the full automorphism groups subject to a weak condition and conjecture that the characterization still holds without the condition. We also present some computational results in relation to hamiltonicity of Cayley graphs, including a generalization of the work on quasi-hamiltonicity by Gutin and Yeo to undirected graphs.

Related

• Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)
• A note on a Cayley graph of S_n
• Cayley graph on symmetric groups with generating block transposition sets
• Automorphism groups of Cayley graphs generated by general transposition sets
• Cayley graphs of order 16p are hamiltonian