Arc-regular cubic graphs of order four times an odd integer
Marston D.E. Conder1
and Yan-Quan Feng2
1Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, 1142 New Zealand
2Mathematics, Beijing Jiaotong University, Beijing, 100044 P.R. China
2Mathematics, Beijing Jiaotong University, Beijing, 100044 P.R. China
DOI: 10.1007/s10801-011-0321-5
Abstract
A graph is arc-regular if its automorphism group acts sharply-transitively on the set of its ordered edges. This paper answers an open question about the existence of arc-regular 3-valent graphs of order 4 m where m is an odd integer. Using the Gorenstein-Walter theorem, it is shown that any such graph must be a normal cover of a base graph, where the base graph has an arc-regular group of automorphisms that is isomorphic to a subgroup of Aut(PSL(2, q)) containing PSL(2, q) for some odd prime-power q. Also a construction is given for infinitely many such graphs-namely a family of Cayley graphs for the groups PSL(2, p 3) where p is an odd prime; the smallest of these has order 9828.
Pages: 21–31
Keywords: keywords arc-regular graph; one-regular graph; symmetric graph; Cayley graph
Full Text: PDF
References
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. Transl. Am. Math. Soc. 158, 247-256 (1971)
3. Cheng, Y., Oxley, J.: On weakly symmetric graphs of order twice a prime. J. Comb. Theory, Ser. B 42, 196-211 (1987)
4. Conder, M.D.E., Dobcsányi, P.: Trivalent symmetric graphs on up to 768 vertices. J. Comb. Math. Comb. Comput. 40, 41-63 (2002)
5. Conder, M.D.E., Lorimer, P.: Automorphism groups of symmetric graphs of valency
3. J. Comb. Theory, Ser. B 47, 60-72 (1989)
6. Conder, M.D.E., Nedela, R.: Symmetric cubic graphs of small girth. J. Comb. Theory, Ser. B 97, 757-768 (2007)
7. Conder, M.D.E., Nedela, R.: A refined classification of symmetric cubic graphs. J. Algebra 322, 722- 740 (2009)
8. Conder, M.D.E., Praeger, C.E.: Remarks on path-transitivity on finite graphs. Eur. J. Comb. 17, 371- 378 (1996)
9. Dickson, L.E.: Linear Groups, with an Exposition of the Galois Field Theory. Dover, New York (1958)
10. Djoković, D.Ž., Miller, G.L.: Regular groups of automorphisms of cubic graphs. J. Comb. Theory, Ser. B 29, 195-230 (1980)
11. 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)
12. Feng, Y.-Q., Kwak, J.H.: Classifying cubic symmetric graphs of order 10p or 10p2. Sci. China Ser. A 49, 300-319 (2006)
13. Feng, Y.-Q., Kwak, J.H.: Cubic symmetric graphs of order a small number times a prime or a prime square. J. Comb. Theory, Ser. B 97, 627-646 (2007)
14. 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)
15. Frucht, R.: A one-regular graph of degree three. Can. J. Math. 4, 240-247 (1952)
16. Gorenstein, D.: Finite Groups, 2nd edn. Chelsea, New York (1980)
17. Giudici, M.: Maximal subgroups of almost simple groups with socle PSL(2, q), preprint. Available at
18. Huppert, B.: Endliche Gruppen I. Springer, Berlin (1967)
19. 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)
20. Lorimer, P.: Vertex-transitive graphs: symmetric graphs of prime valency. J. Graph Theory 8, 55-68 (1984)
21. Lukacs, A., Seifter, N.: Finite contractions of graphs with polynomial growth. Eur. J. Comb. 22, 85-90 (2001)
22. Macbeath, A.M.: Generators of the linear fractional groups. In: Number Theory (Proc. Sympos. Pure Math., vol. XII, 1967), pp. 14-32. Am. Math. Soc., Providence (1969)
23. Malni\check c, A., Maruši\check c, D., Poto\check cnik, P.: Elementary abelian covers of graphs. J. Algebr. Comb. 20, 71-97 (2004)
24. Malni\check c, A., Maruši\check c, D., Seifter, N.: Constructing infinite one-regular graphs. Eur. J. Comb. 20, 845- 853 (1999)
25. Maruši\check c, D.: On vertex symmetric digraphs. Discrete Math. 36, 69-81 (1981)
26. Maruši\check c, D.: A family of one-regular graphs of valency
4. Eur. J. Comb. 18, 59-64 (1997)
27. Maruši\check c, D., Scapellato, R.: Classifying vertex-transitive graphs whose order is a product of two primes. Combinatorica 14, 187-201 (1994)
28. Miller, R.C.: The trivalent symmetric graphs of girth at most six. J. Comb. Theory, Ser. B 10, 163-182 (1971)
29. Praeger, C.E., Wang, R.J., Xu, M.Y.: Symmetric graphs of order a product of two distinct primes. J. Comb. Theory, Ser. B 58, 299-318 (1993)
30. Praeger, C.E., Xu, M.Y.: Vertex-primitive graphs of order a product of two distinct primes. J. Comb. Theory, Ser. B 59, 245-266 (1993)
31. Seifter, N., Woess, W.: Approximating graphs with polynomial growth. Glasg. Math. J. 42, 1-8 (2000)
32. Suzuki, M.: Group Theory I. Springer, New York (1982)
33. Tutte, W.T.: A family of cubical graphs. Proc. Camb. Philos. Soc. 43, 459-474 (1947)
34. Tutte, W.T.: On the symmetry of cubic graphs. Can. J. Math. 11, 621-624 (1959)
35. 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)
36. Wang, C.Q., Zhou, Z.Y.: 4-valent one-regular normal Cayley graphs of dihedral groups. Acta Math.
2. Chao, C.Y.: On the classification of symmetric graphs with a prime number of vertices. Transl. Am. Math. Soc. 158, 247-256 (1971)
3. Cheng, Y., Oxley, J.: On weakly symmetric graphs of order twice a prime. J. Comb. Theory, Ser. B 42, 196-211 (1987)
4. Conder, M.D.E., Dobcsányi, P.: Trivalent symmetric graphs on up to 768 vertices. J. Comb. Math. Comb. Comput. 40, 41-63 (2002)
5. Conder, M.D.E., Lorimer, P.: Automorphism groups of symmetric graphs of valency
3. J. Comb. Theory, Ser. B 47, 60-72 (1989)
6. Conder, M.D.E., Nedela, R.: Symmetric cubic graphs of small girth. J. Comb. Theory, Ser. B 97, 757-768 (2007)
7. Conder, M.D.E., Nedela, R.: A refined classification of symmetric cubic graphs. J. Algebra 322, 722- 740 (2009)
8. Conder, M.D.E., Praeger, C.E.: Remarks on path-transitivity on finite graphs. Eur. J. Comb. 17, 371- 378 (1996)
9. Dickson, L.E.: Linear Groups, with an Exposition of the Galois Field Theory. Dover, New York (1958)
10. Djoković, D.Ž., Miller, G.L.: Regular groups of automorphisms of cubic graphs. J. Comb. Theory, Ser. B 29, 195-230 (1980)
11. 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)
12. Feng, Y.-Q., Kwak, J.H.: Classifying cubic symmetric graphs of order 10p or 10p2. Sci. China Ser. A 49, 300-319 (2006)
13. Feng, Y.-Q., Kwak, J.H.: Cubic symmetric graphs of order a small number times a prime or a prime square. J. Comb. Theory, Ser. B 97, 627-646 (2007)
14. 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)
15. Frucht, R.: A one-regular graph of degree three. Can. J. Math. 4, 240-247 (1952)
16. Gorenstein, D.: Finite Groups, 2nd edn. Chelsea, New York (1980)
17. Giudici, M.: Maximal subgroups of almost simple groups with socle PSL(2, q), preprint. Available at
18. Huppert, B.: Endliche Gruppen I. Springer, Berlin (1967)
19. 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)
20. Lorimer, P.: Vertex-transitive graphs: symmetric graphs of prime valency. J. Graph Theory 8, 55-68 (1984)
21. Lukacs, A., Seifter, N.: Finite contractions of graphs with polynomial growth. Eur. J. Comb. 22, 85-90 (2001)
22. Macbeath, A.M.: Generators of the linear fractional groups. In: Number Theory (Proc. Sympos. Pure Math., vol. XII, 1967), pp. 14-32. Am. Math. Soc., Providence (1969)
23. Malni\check c, A., Maruši\check c, D., Poto\check cnik, P.: Elementary abelian covers of graphs. J. Algebr. Comb. 20, 71-97 (2004)
24. Malni\check c, A., Maruši\check c, D., Seifter, N.: Constructing infinite one-regular graphs. Eur. J. Comb. 20, 845- 853 (1999)
25. Maruši\check c, D.: On vertex symmetric digraphs. Discrete Math. 36, 69-81 (1981)
26. Maruši\check c, D.: A family of one-regular graphs of valency
4. Eur. J. Comb. 18, 59-64 (1997)
27. Maruši\check c, D., Scapellato, R.: Classifying vertex-transitive graphs whose order is a product of two primes. Combinatorica 14, 187-201 (1994)
28. Miller, R.C.: The trivalent symmetric graphs of girth at most six. J. Comb. Theory, Ser. B 10, 163-182 (1971)
29. Praeger, C.E., Wang, R.J., Xu, M.Y.: Symmetric graphs of order a product of two distinct primes. J. Comb. Theory, Ser. B 58, 299-318 (1993)
30. Praeger, C.E., Xu, M.Y.: Vertex-primitive graphs of order a product of two distinct primes. J. Comb. Theory, Ser. B 59, 245-266 (1993)
31. Seifter, N., Woess, W.: Approximating graphs with polynomial growth. Glasg. Math. J. 42, 1-8 (2000)
32. Suzuki, M.: Group Theory I. Springer, New York (1982)
33. Tutte, W.T.: A family of cubical graphs. Proc. Camb. Philos. Soc. 43, 459-474 (1947)
34. Tutte, W.T.: On the symmetry of cubic graphs. Can. J. Math. 11, 621-624 (1959)
35. 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)
36. Wang, C.Q., Zhou, Z.Y.: 4-valent one-regular normal Cayley graphs of dihedral groups. Acta Math.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition