EDGE-TRANSITIVITY OF CAYLEY GRAPHS GENERATED BY TRANSPOSITIONS

被引：3

作者：

Ganesan, Ashwin ^{[1
]}

机构：

[1] 53 Deonar House Deonar Village Rd, Mumbai 400088, Maharashtra, India

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2016年 / 36卷 / 04期

关键词：

Cayley graphs; transpositions; automorphisms of graphs; edge transitive graphs; line graphs; Whitney's isomorphism theorem; AUTOMORPHISM-GROUPS;

D O I：

10.7151/dmgt.1903

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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) is an element of 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.

引用

页码：1035 / 1042

页数：8

共 20 条

[1] A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].

AKERS, SB ;

KRISHNAMURTHY, B .

IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) :555-566

[2]

[Anonymous], 1927, Fundamenta Mathematicae

[3]

[Anonymous], 1998, GRAD TEXT M

[4]

[Anonymous], 2001, ALGEBRAIC GRAPH THEO, DOI DOI 10.1007/978-1-4613-0163-9

[5]

Biggs N.L., 1993, Algebraic graph theory

[6] Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets [J].

Feng, YQ .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (01) :67-72

[7] Automorphism group of the complete transposition graph [J].

Ganesan, Ashwin .

JOURNAL OF ALGEBRAIC COMBINATORICS, 2015, 42 (03) :793-801

[8] Automorphism groups of Cayley graphs generated by connected transposition sets [J].

Ganesan, Ashwin .

DISCRETE MATHEMATICS, 2013, 313 (21) :2482-2485

[9]

Heydemann M.-C., 1999, Technical Report No 3624

[10]

Heydemann MC, 1997, NATO ADV SCI I C-MAT, V497, P167

← 1 2 →