Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps

DOI10.1016/J.DISC.2016.06.014zbMATH Open1347.05091arXiv1511.07268OpenAlexW2964116325MaRDI QIDQ329537FDOQ329537

Authors: Annachiara Korchmaros, István Kovács 

Publication date: 21 October 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: This paper deals with the Cayley graph $mathrmCay(mathrm{Sym}_n,T_n),$ where the generating set consists of all block transpositions. A motivation for the study of these particular Cayley graphs comes from current research in Bioinformatics. As the main result, we prove that Aut$(mathrmCay(mathrm{Sym}_n,T_n))$ is the product of the left translation group by a dihedral group $mathsf{D}_{n+1}$ of order $2(n+1)$. The proof uses several properties of the subgraph $Gamma$ of $mathrmCay(mathrm{Sym}_n,T_n)$ induced by the set $T_n$. In particular, $Gamma$ is a $2(n-2)$-regular graph whose automorphism group is $mathsf{D}_{n+1},$ $Gamma$ has as many as $n+1$ maximal cliques of size $2,$ and its subgraph $Gamma(V)$ whose vertices are those in these cliques is a $3$-regular, Hamiltonian, and vertex-transitive graph. A relation of the unique cyclic subgroup of $mathsf{D}_{n+1}$ of order $n+1$ with regular Cayley maps on $mathrm{Sym}_n$ is also discussed. It is shown that the product of the left translation group by the latter group can be obtained as the automorphism group of a non-$t$-balanced regular Cayley map on $mathrm{Sym}_n$.

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

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 transposition graph
• Automorphism groups of a class of cubic Cayley graphs on symmetric groups
• On the automorphism group of Cayley graphs generated by transpositions

zbMATH Keywords

Cayley graphsymmetric groupCayley mapregular mapblock transpositiongraph automorphism

Mathematics Subject Classification ID

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

Cites Work

• Endliche Gruppen I
• Combinatorics of permutations
• Combinatorics of genome rearrangements.
• Title not available (Why is that?)
• Skew-morphisms of regular Cayley maps
• Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets
• On a Theorem of Holder
• Automorphism groups of Cayley graphs generated by connected transposition sets
• Automorphism groups of the Pancake graphs
• Title not available (Why is that?)
• On Hultman numbers
• Title not available (Why is that?)
• Sorting a bridge hand
• The `Butterfly effect' in Cayley graphs with applications to genomics.
• Regular \(t\)-balanced Cayley maps
• Some problems on Cayley graphs

Cited In (5)

• Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets
• Sorting permutations with transpositions in \(O(n^3)\) amortized time
• Automorphism groups of Cayley graphs generated by connected transposition sets
• Some properties of alternating group networks
• On the automorphism group of Cayley graphs generated by transpositions

Uses Software

• GAP

This page was built for publication: Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps

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