Edge-transitivity of Cayley graphs generated by transpositions

DOI10.7151/DMGT.1903MaRDI QIDQ339495zbMATH OpenOpenAlexFDO

Authors Ashwin Ganesan

Publication date 11 November 2016

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 1054728 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (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?)
• A group-theoretic model for symmetric interconnection networks
• Automorphism group of the complete transposition graph
• Automorphism groups of Cayley graphs generated by connected transposition sets
• Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets
• Cayley graphs as classifiers for data mining: the influence of asymmetries
• Complete rotations in Cayley graphs
• Congruent Graphs and the Connectivity of Graphs
• Connectivity of transitive graphs
• Graph derivatives
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• Transposition networks as a class of fault-tolerant robust networks
• Über den Zusammenhang symmetrischer Graphen

Cited in

(13)

• Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets
• scientific article; zbMATH DE number 5139492 (Why is no real title available?)
• 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
• Automorphism groups of Cayley graphs generated by general transposition sets
• Automorphism groups of Cayley graphs generated by connected transposition sets
• 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)