Edge-Transitivity of Cayley Graphs Generated by Transpositions

• Volume: 36, Issue: 4, page 1035-1042
• ISSN: 2083-5892

top

Abstract

top
Let S be a set of transpositions generating the symmetric group Sn (n ≥ 5). The transposition graph of S is defined to be the graph with vertex set {1, . . . , n}, and with vertices i and j being adjacent in T(S) whenever (i, j) ∈ S. 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(Sn, S) is edge-transitive.

How to cite

top

Ashwin Ganesan. "Edge-Transitivity of Cayley Graphs Generated by Transpositions." Discussiones Mathematicae Graph Theory 36.4 (2016): 1035-1042. <http://eudml.org/doc/287145>.

@article{AshwinGanesan2016,
abstract = {Let S be a set of transpositions generating the symmetric group Sn (n ≥ 5). The transposition graph of S is defined to be the graph with vertex set \{1, . . . , n\}, and with vertices i and j being adjacent in T(S) whenever (i, j) ∈ S. 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(Sn, S) is edge-transitive.},
author = {Ashwin Ganesan},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Cayley graphs; transpositions; automorphisms of graphs; edge-transitive graphs; line graphs; Whitney’s isomorphism theorem; Whitney's isomorphism theorem},
language = {eng},
number = {4},
pages = {1035-1042},
title = {Edge-Transitivity of Cayley Graphs Generated by Transpositions},
url = {http://eudml.org/doc/287145},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Ashwin Ganesan
TI - Edge-Transitivity of Cayley Graphs Generated by Transpositions
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 4
SP - 1035
EP - 1042
AB - Let S be a set of transpositions generating the symmetric group Sn (n ≥ 5). The transposition graph of S is defined to be the graph with vertex set {1, . . . , n}, and with vertices i and j being adjacent in T(S) whenever (i, j) ∈ S. 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(Sn, S) is edge-transitive.
LA - eng
KW - Cayley graphs; transpositions; automorphisms of graphs; edge-transitive graphs; line graphs; Whitney’s isomorphism theorem; Whitney's isomorphism theorem
UR - http://eudml.org/doc/287145
ER -

NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.