Edge-transitivity of Cayley graphs generated by transpositions

DOI10.7151/DMGT.1903zbMATH Open1350.05059arXiv1511.05430OpenAlexW2963607293MaRDI QIDQ339495FDOQ339495

Authors: Ashwin Ganesan 

Publication date: 11 November 2016

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Abstract: Let $S$ be a set of transpositions generating the symmetric group $S_n$. The transposition graph of $S$ is defined to be the graph with vertex set $1,ldots,n$, and with vertices $i$ and $j$ being adjacent in $T(S)$ whenever $(i,j)inS$. In the present note, it is proved that two transposition graphs are isomorphic if and only if the corresponding two Cayley graphs are isomorphic. It is also proved that the transposition graph $T(S)$ is edge-transitive if and only if the Cayley graph $Cay(S_n,S)$ is edge-transitive.

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

Recommendations

• Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets
• Automorphism groups of Cayley graphs generated by connected transposition sets
• scientific article; zbMATH DE number 5139492
• Automorphism group of the complete transposition graph
• The edge transitivity and Hamiltonian property of a class of Cayley graphs

zbMATH Keywords

Cayley graphsline graphsedge-transitive graphsautomorphisms of graphstranspositionsWhitney's isomorphism theorem

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Symmetric groups (20B30) Group actions on combinatorial structures (05E18)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph derivatives
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• A group-theoretic model for symmetric interconnection networks
• Title not available (Why is that?)
• Congruent Graphs and the Connectivity of Graphs
• Title not available (Why is that?)
• Cayley graphs as classifiers for data mining: the influence of asymmetries
• Automorphism group of the complete transposition graph
• Transposition networks as a class of fault-tolerant robust networks
• Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets
• Automorphism groups of Cayley graphs generated by connected transposition sets
• Über den Zusammenhang symmetrischer Graphen
• Title not available (Why is that?)
• Connectivity of transitive graphs
• Complete rotations in Cayley graphs

Cited In (11)

• Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets
• Title not available (Why is that?)
• Bipancyclic properties of Cayley graphs generated by transpositions
• The generalized 3-connectivity of Cayley graphs on symmetric groups generated by trees and cycles
• The (n,k)-Modified-Bubble-Sort Graph: A Generalized Modified-Bubble-Sort Graph
• Reliability evaluation of modified bubble-sort graph networks based on structure fault pattern
• Presentations of groups generated by transpositions
• Finite edge-transitive Cayley graphs and rotary Cayley maps
• The (E)FTSM-(edge) Connectivity of Cayley Graphs Generated by Transposition Trees
• A note on characterization of the induced matching extendable Cayley graphs generated by transpositions
• Fault tolerant supergraphs with automorphisms

This page was built for publication: Edge-transitivity of Cayley graphs generated by transpositions

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