Automorphism group of the complete transposition graph

DOI10.1007/S10801-015-0602-5MaRDI QIDQ887942zbMATH OpenOpenAlexFDO

Authors Ashwin Ganesan

Publication date 4 November 2015

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.7363

zbMATH Keywords

automorphisms of graphscomplete transposition graphnormal Cayley graphs

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Symmetric groups (20B30)

Abstract: The complete transposition graph is defined to be the graph whose vertices are the elements of the symmetric group $S_n$, and two vertices $alpha$ and $$ are adjacent in this graph iff there is some transposition $(i,j)$ such that $$. Thus, the complete transposition graph is the Cayley graph $Cay(S_n,S)$ of the symmetric group generated by the set $S$ of all transpositions. An open problem in the literature is to determine which Cayley graphs are normal. It was shown recently that the Cayley graph generated by 4 cyclically adjacent transpositions is not normal. In the present paper, it is proved that the complete transposition graph is not a normal Cayley graph, for all $nge3$. Furthermore, the automorphism group of the complete transposition graph is shown to equal [ Aut(Cay(S_n,S)) = (R(S_n) times Inn(S_n)) times mathbb{Z}_2, ] where $R(S_n)$ is the right regular representation of $S_n$, $Inn(S_n)$ is the group of inner automorphisms of $S_n$, and $mathbb{Z}_2=langlehangle$, where $h$ is the map $alphamapstoalph{a}^{-1}$.

Recommendations

• Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets
• Automorphism groups of Cayley graphs generated by connected transposition sets
• Automorphism group of the complete alternating group graph
• On the automorphism group of Cayley graphs generated by transpositions
• Automorphism groups of a class of cubic Cayley graphs on symmetric groups

Cites work

• Automorphism group of the derangement graph
• Automorphism groups and isomorphisms of Cayley digraphs
• Automorphism groups of Cayley graphs generated by connected transposition sets
• Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets
• Automorphism groups of the Pancake graphs
• Bisection width of transposition graphs
• Congruent Graphs and the Connectivity of Graphs
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3739805 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• scientific article; zbMATH DE number 7491960 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• On the full automorphism group of a graph
• The automorphism group of the alternating group graph

Cited in

(27)

• Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time
• Automorphism group of the varietal hypercube graph
• Fault tolerant supergraphs with automorphisms
• Automorphism group of the complete alternating group graph
• Cayley properties of the line graphs induced by consecutive layers of the hypercube
• On the automorphism groups of connected bipartite irreducible graphs
• A method to solve conditional optimization problems with quadratic objective functions on the set of permutations
• Extremal even-cycle-free subgraphs of the complete transposition graphs
• Some properties of alternating group networks
• Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets
• On Cayley representations of central Cayley graphs over almost simple groups
• Disjoint Hamilton cycles in transposition graphs
• On the automorphism group of Cayley graphs generated by transpositions
• Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps
• Edge-transitivity of Cayley graphs generated by transpositions
• Automorphism groups of Cayley graphs generated by connected transposition sets
• scientific article; zbMATH DE number 2076912 (Why is no real title available?)
• Some remarks on the square graph of the hypercube
• Complete rotations in Cayley graphs
• Presentations of groups generated by transpositions
• The symmetry property of (n,k)‐arrangement graph
• Automorphism group of the derangement graph
• Automorphism groups of Cayley graphs generated by general transposition sets
• On automorphism groups of the conjugacy class type Cayley graphs on the symmetric and alternating groups
• Generalized Grassmann graphs of orthogonal decompositions of Hilbert spaces
• \(\{ 1, 2, 3 \}\)-extra connectivity of Cayley graphs generated by \(k\)-trees
• Exploiting symmetries in optimal quantum circuit design

This page was built for publication: Automorphism group of the complete transposition graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q887942)