Edge-Transitivity of Cayley Graphs Generated by Transpositions

Ganesan, Ashwin

Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 1035-1042.

Résumé

Let S be a set of transpositions generating the symmetric group S_n (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(S_n, S) is edge-transitive.

Détail

Keywords: Cayley graphs, transpositions, automorphisms of graphs, edge-transitive graphs, line graphs, Whitney’s isomorphism theorem

Bibliographie

[1] S.B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput. 38 (1989) 555-566. doi: 10.1109/12.21148

[2] N.L. Biggs, Algebraic Graph Theory (2nd Edition, Cambridge University Press, Cambridge, 1993).

[3] B. Bollobás, Modern Graph Theory, Graduate Texts in Mathematics 184 (Springer, New York, 1998).

[4] Y.-Q. Feng, Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets, J. Combin. Theory Ser. B 96 (2006) 67-72. doi: 10.1016/j.jctb.2005.06.010

[5] A. Ganesan, Automorphism groups of Cayley graphs generated by connected transposition sets, Discrete Math. 313 (2013) 2482-2485. doi: 10.1016/j.disc.2013.07.013

[6] A. Ganesan, Automorphism group of the complete transposition graph, J. Algebraic Combin. 42 (2015) 793-801. doi: 10.1007/s10801-015-0602-5

[7] C. Godsil and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics 207 (Springer, New York, 2001).

[8] M.-C. Heydemann, Cayley graphs and interconnection networks, in: Hahn and Sabidussi (Ed(s)), Graph Symmetry: Algebraic Methods and Applications (Kluwer Academic Publishers, Dordrecht 1997) 167-224.

[9] M.-C. Heydemann, N. Marlin, and S. Pérennes, Cayley graphs with complete rotations, Technical Report No 3624, INRIA (1999).

[10] A. Kelarev, J. Ryan and J. Yearwood, Cayley graphs as classifiers for data mining: The influence of asymmetries, Discrete Math. 309 (2009) 5360-5369. doi: 10.1016/j.disc.2008.11.030

[11] E. Konstantinova, Lecture notes on some problems on Cayley graphs, University of Primorska (2012).

[12] S. Lakshmivarahan, J.-S. Jwo and S.K. Dhall, Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey, Parallel Comput. 19 (1993) 361-407. doi: 10.1016/0167-8191(93)90054-O

[13] S. Latifi and P.K. Srimani, Transposition networks as a class of fault-tolerant robust networks, Computer Science Technical Report CS-95-104, Colorado State University (1995).

[14] S. Latifi and P.K. Srimani, Transposition networks as a class of fault-tolerant robust networks, IEEE Trans. Comput. (1996) 230-238. doi: 10.1109/12.485375

[15] W. Mader, Über den Zusammenhang symmetrischer Graphen, Arch. Math. (Basel) 21 (1970) 331-336. doi: 10.1007/BF01220924

[16] K. Menger, Zur allgemeinen Kurventheorie, Fund. Math. 10 (1927) 96-115.

[17] G. Sabidussi, Graph derivatives, Math. Z. 76 (1961) 385-401. doi: 10.1007/BF01210984

[18] M.E. Watkins, Connectivity of transitive graphs, J. Combin. Theory 8 (1970) 23-29. doi: 10.1016/S0021-9800(70)80005-9

[19] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932) 150-168. doi: 10.2307/2371086

[20] Z. Zhang and Q. Huang, Automorphism groups of bubble-sort graphs and modified bubble-sort graphs, Adv. Math. 34 (2005) 441-447, in China. doi: 10.11845/sxjz.2005.34.04.0441