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

DOI10.1016/J.DISC.2016.06.014MaRDI QIDQ329537zbMATH OpenOpenAlexFDO

Authors Annachiara Korchmaros, István Kovács

Publication date 21 October 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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$.

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

Cites work

• scientific article; zbMATH DE number 2149408 (Why is no real title available?)
• scientific article; zbMATH DE number 863496 (Why is no real title available?)
• scientific article; zbMATH DE number 4189771 (Why is no real title available?)
• 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
• Combinatorics of genome rearrangements.
• Combinatorics of permutations
• Endliche Gruppen I
• On Hultman numbers
• On a Theorem of Holder
• Regular \(t\)-balanced Cayley maps
• Skew-morphisms of regular Cayley maps
• Some problems on Cayley graphs
• Sorting a bridge hand
• The `Butterfly effect' in Cayley graphs with applications to genomics.

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

Describes a project that uses

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)