JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 29, No 4 (2009)

Jin-Xin Zhou and Yan-Quan Feng

Beijing Jiaotong University Department of Mathematics Beijing 100044 China

A graph is one-regular if its automorphism group acts regularly on the set of its arcs. In this article a complete classification of tetravalent one-regular graphs of order twice a product of two primes is given. It follows from this classification that with the exception of four graphs of orders 12 and 30, all such graphs are Cayley graphs on Abelian, dihedral, or generalized dihedral groups.

1. Bosma, W., Cannon, C., Playoust, C.: The MAGMA algebra system, I: the user language. J. Symb. Comput. 24, 235-265 (1997)
2. Chao, C.Y.: On the classification of symmetric graphs with a prime number of vertices. Tran. Am. Math. Soc. 158, 247-256 (1971)
3. Cheng, Y., Oxley, J.: On weakly symmetric graphs of order twice a prime. J. Comb. Theory B 42, 196-211 (1987)
4. Conder, M.D.E., Praeger, C.E.: Remarks on path-transitivity on finite graphs. Eur. J. Comb. 17, 371- 378 (1996)
5. Djoković, D.Ž, Miller, G.L.: Regular groups of automorphisms of cubic graphs. J. Comb. Theory B 29, 195-230 (1980)
6. Feng, Y.-Q., Kwak, J.H.: One-regular cubic graphs of order a small number times a prime or a prime square. J. Aust. Math. Soc. 76, 345-356 (2004)
7. Feng, Y.-Q., Kwak, J.H.: Classifying cubic symmetric graphs of order 10p or 10p2. Sci. China A 49, 300-319 (2006)
8. Feng, Y.-Q., Kwak, J.H.: Cubic symmetric graphs of order a small number times a prime or a prime square. J. Comb. Theory B 97, 627-646 (2007)
9. Feng, Y.-Q., Kwak, J.H., Wang, K.S.: Classifying cubic symmetric graphs of order 8p or 8p2. Eur. J. Comb. 26, 1033-1052 (2005)
10. Frucht, R.: A one-regular graph of degree three. Can. J. Math. 4, 240-247 (1952)
11. Gardiner, A., Praeger, C.E.: On 4-valent symmetric graphs. Eur. J. Comb. 15, 375-381 (1994)
12. Gardiner, A., Praeger, C.E.: A characterization of certain families of 4-valent symmetric graphs. Eur. J. Comb. 15, 383-397 (1994)
13. Gorenstein, D.: Finite Simple Groups. Plenum, New York (1982)
14. Guo, D.C.: A classification of symmetric graphs of order
30. Australas. J. Comb. 15, 277-294 (1997)
15. Huppert, B.: Endliche Gruppen I. Springer, Berlin (1967)
16. Kwak, J.H., Oh, J.M.: One-regular normal Cayley graphs on dihedral groups of valency 4 or 6 with cyclic vertex stabilizer. Acta Math. Sin. Engl. Ser. 22, 1305-1320 (2006)
17. Li, C.H., Lu, Z.P., Maruši\check c, D.: On primitive permutation groups with small suborbits and their orbital graphs. J. Algebra 279, 749-770 (2004)
18. Lorimer, P.: Vertex-transitive graphs: symmetric graphs of prime valency. J. Graph Theory 8, 55-68 (1984)
19. Lukacs, A., Seifter, N.: Finite contractions of graphs with polynomial growth. Eur. J. Comb. 22, 85-90 (2001)
20. Malni\check c, A., Maruši\check c, D., Poto\check cnik, P., Wang, C.: An infinite family of cubic edgebut not vertextransitive graphs. Discrete Math. 280, 133-148 (2004)
21. Malni\check c, A., Maruši\check c, D., Seifter, N.: Constructing infinite one-regular graphs. Eur. J. Comb. 20, 845- 853 (1999)
22. Maruši\check c, D.: On vertex symmetric digraphs. Discrete Math. 36, 69-81 (1981)
23. Maruši\check c, D.: A family of one-regular graphs of valency
4. Eur. J. Comb. 18, 59-64 (1997)
24. Maruši\check c, D., Scapellato, R.: Classifying vertex-transitive graphs whose order is a product of two primes. Combinatorica 14, 187-201 (1994)
25. McKay, B.D.: Transitive graphs with fewer than 20 vertices. Math. Comput. 33, 1101-1121 (1979)
26. Miller, R.C.: The trivalent symmetric graphs of girth at most six. J. Comb. Theory B 10, 163-182 (1971)
27. Praeger, C.E., Wang, R.J., Xu, M.Y.: Symmetric graphs of order a product of two distinct primes. J. Comb. Theory B 58, 299-318 (1993)
28. Praeger, C.E., Xu, M.Y.: A characterization of a class of symmetric graphs of twice prime valency. Eur. J. Comb. 10, 91-102 (1989)
29. Praeger, C.E., Xu, M.Y.: Vertex-primitive graphs of order a product of two distinct primes. J. Comb. Theory B 59, 245-266 (1993)
30. Sabidussi, B.O.: Vertex-transitive graphs. Monash Math. 68, 426-438 (1964)
31. Seifter, N., Woess, W.: Approximating graphs with polynomial growth. Glasgow Math. J. 42, 1-8 (2000)
32. Wang, C.Q., Xu, M.Y.: Non-normal one-regular and 4-valent Cayley graphs of dihedral groups D2n. Eur. J. Comb. 27, 750-766 (2006)
33. Wang, C.Q., Zhou, Z.Y.: 4-valent one-regular normal Cayley graphs of dihedral groups. Acta Math.