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 graphsnormal Cayley graphscomplete transposition graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) 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

• 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?)
• 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
• On the full automorphism group of a graph
• The automorphism group of the alternating group graph

Cited in

(23)

• Complete rotations in Cayley graphs
• On the automorphism groups of connected bipartite irreducible graphs
• Presentations of groups generated by transpositions
• Disjoint Hamilton cycles in transposition graphs
• Automorphism groups of Cayley graphs generated by connected transposition sets
• The symmetry property of (n,k)‐arrangement graph
• Cayley properties of the line graphs induced by consecutive layers of the hypercube
• Some properties of alternating group networks
• 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 derangement graph
• On Cayley representations of central Cayley graphs over almost simple groups
• 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
• Automorphism group of the complete alternating group graph
• Automorphism groups of Cayley graphs generated by general transposition sets
• Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps
• Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets
• scientific article; zbMATH DE number 2076912 (Why is no real title available?)
• Some remarks on the square graph of the hypercube
• Edge-transitivity of Cayley graphs generated by transpositions
• On the automorphism group of Cayley graphs generated by transpositions

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)