One-regular normal Cayley graphs on dihedral groups of valency 4 or 6 with cyclic vertex stabilizer

被引:30
作者
Kwak, Jin Ho [1 ]
Oh, Ju Mok [1 ]
机构
[1] Pohang Univ Sci & Technol, Pohang 790784, South Korea
关键词
one-regular graph; Cayley graph; dihedral group; half-transitive graph;
D O I
10.1007/s10114-005-0752-9
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A graph G is one-regular if its automorphism group Aut(G) acts transitively and semiregularly on the arc set. A Cayley graph Cay(Gamma, S) is normal if Gamma is a normal subgroup of the full automorphism group of Cay(Gamma, S). Xu, M. Y., Xu, J. (Southeast Asian Bulletin of Math., 25, 355-363 (2001)) classified one-regular Cayley graphs of valency at most 4 on finite abelian groups. Marusic, D., Pisanski, T. (Croat. Chemica Acta, 73, 969-981 (2000)) classified cubic one-regular Cayley graphs on a dihedral group, and all of such graphs turn out to be normal. In this paper, we classify the 4-valent one-regular normal Cayley graphs G on a dihedral group whose vertex stabilizers in Aut(G) are cyclic. A classification of the same kind of graphs of valency 6 is also discussed.
引用
收藏
页码:1305 / 1320
页数:16
相关论文
共 21 条
[1]   CONSTRUCTING GRAPHS WHICH ARE 1/2-TRANSITIVE [J].
ALSPACH, B ;
MARUSIC, D ;
NOWITZ, L .
JOURNAL OF THE AUSTRALIAN MATHEMATICAL SOCIETY SERIES A-PURE MATHEMATICS AND STATISTICS, 1994, 56 :391-402
[2]  
Biggs N., 1993, ALGEBRAIC GRAPH THEO
[3]   ON WEAKLY SYMMETRICAL GRAPHS OF ORDER TWICE A PRIME [J].
CHENG, Y ;
OXLEY, J .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1987, 42 (02) :196-211
[4]   REGULAR GROUPS OF AUTOMORPHISMS OF CUBIC GRAPHS [J].
DJOKOVIC, DZ ;
MILLER, GL .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1980, 29 (02) :195-230
[5]   A ONE-REGULAR GRAPH OF DEGREE 3 [J].
FRUCHT, R .
CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1952, 4 (02) :240-247
[6]   A CHARACTERIZATION OF CERTAIN FAMILIES OF 4-VALENT SYMMETRICAL GRAPHS [J].
GARDINER, A ;
PRAEGER, CE .
EUROPEAN JOURNAL OF COMBINATORICS, 1994, 15 (04) :383-397
[7]   ON 4-VALENT SYMMETRICAL GRAPHS [J].
GARDINER, A ;
PRAEGER, CE .
EUROPEAN JOURNAL OF COMBINATORICS, 1994, 15 (04) :375-381
[8]   Characterisation of graphs which underlie regular maps on closed surfaces [J].
Gardiner, A ;
Nedela, R ;
Sirán, J ;
Skoviera, M .
JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 1999, 59 :100-108
[9]   Infinitely many finite one-regular graphs of any even valency [J].
Kwak, JH ;
Oh, JM .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2004, 90 (01) :185-191
[10]   Constructing infinite one-regular graphs [J].
Malnic, A ;
Marusic, D ;
Seifter, N .
EUROPEAN JOURNAL OF COMBINATORICS, 1999, 20 (08) :845-853