Tetravalent half-arc-transitive graphs of order 2 pq
Yan-Quan Feng
, Jin Ho Kwak
, Xiuyun Wang
and Jin-Xin Zhou
DOI: 10.1007/s10801-010-0257-1
Abstract
A graph is half-arc-transitive if its automorphism group acts transitively on its vertex set, edge set, but not arc set. Let p and q be primes. It is known that no tetravalent half-arc-transitive graphs of order 2 p 2 exist and a tetravalent half-arc-transitive graph of order 4 p must be non-Cayley; such a non-Cayley graph exists if and only if p - 1 is divisible by 8 and it is unique for a given order. Based on the constructions of tetravalent half-arc-transitive graphs given by Marušič (J. Comb. Theory B 73:41-76, 1998), in this paper the connected tetravalent half-arc-transitive graphs of order 2 pq are classified for distinct odd primes p and q.
Pages: 543–553
Keywords: keywords Cayley graph; vertex-transitive graph; half-arc-transitive graph
Full Text: PDF
References
1. Alspach, B., Maruši\check c, D., Nowitz, L.: Constructing graphs which are 1/2-transitive. J. Aust. Math. Soc. A 56, 391-402 (1994)
2. Alspach, B., Xu, M.Y.: 1/2-transitive graphs of order 3p. J. Algebr. Comb. 1, 275-282 (1992)
3. Babai, L.: Isomorphism problem for a class of point-symmetric structures. Acta Math. Acad. Sci. Hung. 29, 329-336 (1977)
4. Biggs, N.: Algebraic Graph Theory, 2nd edn. Cambridge University Press, Cambridge (1993)
5. Bouwer, I.Z.: Vertexand edge-transitive but not 1-transitive graphs. Can. Math. Bull. 13, 231-237 (1970)
6. Chao, C.Y.: On the classification of symmetric graphs with a prime number of vertices. Trans. Am. Math. Soc. 158, 247-256 (1971)
7. Cheng, Y., Oxley, J.: On weakly symmetric graphs of order twice a prime. J. Comb. Theory B 42, 196-211 (1987)
8. Conder, M.D.E., Maruši\check c, D.: A tetravalent half-arc-transitive graph with non-abelian vertex stabilizer. J. Comb. Theory B 88, 67-76 (2003)
9. Du, S.F., Xu, M.Y.: Vertex-primitive 1 -arc-transitive graphs of smallest order. Commun. Algebra 27, 2 163-171 (1999)
10. Fang, X.G., Li, C.H., Xu, M.Y.: On edge-transitive Cayley graphs of valency
4. Eur. J. Comb. 25, 1107-1116 (2004)
11. Feng, Y.-Q., Kwak, J.H., Xu, M.Y., Zhou, J.-X.: Tetravalent half-arc-transitive graphs of order p4. Eur. J. Comb. 29, 555-567 (2008)
12. Feng, Y.-Q., Kwak, J.H., Zhou, C.X.: Constructing even radius tightly attached half-arc-transitive graphs of valency four. J. Algebr. Comb. 26, 431-451 (2007)
13. Feng, Y.-Q., Wang, K.S., Zhou, C.X.: Tetravalent half-transitive graphs of order 4p. Eur. J. Comb. 28, 726-733 (2007)
14. Gorenstein, D.: Finite Simple Groups. Plenum, New York (1982)
15. Holt, D.F.: A graph which is edge transitive but not arc transitive. J. Graph Theory 5, 201-204 (1981)
16. 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)
17. Li, C.H., Lu, Z.P., Zhang, H.: Tetravalent edge-transitive Cayley graphs with odd number of vertices. J. Comb. Theory B 96, 164-181 (2006)
18. Li, C.H., Sim, H.S.: On half-transitive metacirculent graphs of prime-power order. J. Comb. Theory B 81, 45-57 (2001)
19. Malni\check c, A., Maruši\check c, D.: Constructing 4-valent 1 -transitive graphs with a nonsolvable automorphism 2 group. J. Comb. Theory B 75, 46-55 (1999)
20. Malni\check c, A., Maruši\check c, D.: Constructing 1 -arc-transitive graphs of valency 4 and vertex stabilizer 2 Z2 \times Z2. Discrete Math. 245, 203-216 (2002)
21. Maruši\check c, D.: Half-transitive groups actions on finite graphs of valency
4. J. Comb. Theory B 73, 41-76 (1998)
22. Maruši\check c, D., Nedela, R.: Finite graphs of valency 4 and girth 4 admitting half-transitive group actions. J. Aust. Math. Soc. 73, 155-170 (2002)
23. Maruši\check c, D., Nedela, R.: Partial line graph operator and half-arc-transitive group actions. Math. Slovaca 51, 241-257 (2001)
24. Maruši\check c, D., Nedela, R.: Maps and half-transitive graphs of valency
4. Eur. J. Comb. 19, 345-354 (1998)
25. Maruši\check c, D., Praeger, C.E.: Tetravalent graphs admitting half-transitive group action: alternating cycles. J. Comb. Theory B 75, 188-205 (1999)
26. Maruši\check c, D., Šparl, P.: On quartic half-arc-transitive metacirculants. J. Algebr. Comb. 28, 365-395 (2008)
27. Maruši\check c, D., Waller, A.: Half-transitive graphs of valency 4 with prescribed attachment numbers. J. Graph Theory 34, 89-99 (2000)
28. Maruši\check c, D., Xu, M.Y.: A 1 -transitive graph of valency 4 with a nonsolvable group of automorphisms. 2 J. Graph Theory 25, 133-138 (1997)
29. Robinson, D.J.: A Course in the Theory of Groups. Springer, New York (1982)
30. Šparl, P.: A classification of tightly attached half-arc-transitive graphs of valency
4. J. Comb. Theory B 98, 1076-1108 (2008)
31. Tutte, W.: Connectivity in Graphs. University of Toronto Press, Toronto (1966)
32. Taylor, D.E., Xu, M.Y.: Vertex-primitive 1/2-transitive graphs. J. Aust. Math. Soc. A 57, 113-124 (1994)
33. Wang, R.J.: Half-transitive graphs of order a product of two distinct primes. Commun. Algebra 22, 915-927 (1994)
34. Wang, X.Y., Feng, Y.-Q.: There exists no tetravalent half-arc-transitive graph of order 2p2. Discrete Math. 310, 1721-1724 (2010)
35. Wang, X.Y., Feng, Y.-Q.: Hexavalent half-arc-transitive graphs of order 4p. Eur. J. Comb. 30, 1263- 1270 (2009)
36. Wilson, S., Poto\check nik, P.: A Census of edge-transitive tetravalent graphs: Mini-Census, available at
37. Xu, M.Y.: Half-transitive graphs of prime-cube order. J. Algebr. Comb. 1, 275-282 (1992)
38. Zhou, C.X., Feng, Y.-Q.: An infinite family of tetravalent half-arc-transitive graphs. Discrete Math.
2. Alspach, B., Xu, M.Y.: 1/2-transitive graphs of order 3p. J. Algebr. Comb. 1, 275-282 (1992)
3. Babai, L.: Isomorphism problem for a class of point-symmetric structures. Acta Math. Acad. Sci. Hung. 29, 329-336 (1977)
4. Biggs, N.: Algebraic Graph Theory, 2nd edn. Cambridge University Press, Cambridge (1993)
5. Bouwer, I.Z.: Vertexand edge-transitive but not 1-transitive graphs. Can. Math. Bull. 13, 231-237 (1970)
6. Chao, C.Y.: On the classification of symmetric graphs with a prime number of vertices. Trans. Am. Math. Soc. 158, 247-256 (1971)
7. Cheng, Y., Oxley, J.: On weakly symmetric graphs of order twice a prime. J. Comb. Theory B 42, 196-211 (1987)
8. Conder, M.D.E., Maruši\check c, D.: A tetravalent half-arc-transitive graph with non-abelian vertex stabilizer. J. Comb. Theory B 88, 67-76 (2003)
9. Du, S.F., Xu, M.Y.: Vertex-primitive 1 -arc-transitive graphs of smallest order. Commun. Algebra 27, 2 163-171 (1999)
10. Fang, X.G., Li, C.H., Xu, M.Y.: On edge-transitive Cayley graphs of valency
4. Eur. J. Comb. 25, 1107-1116 (2004)
11. Feng, Y.-Q., Kwak, J.H., Xu, M.Y., Zhou, J.-X.: Tetravalent half-arc-transitive graphs of order p4. Eur. J. Comb. 29, 555-567 (2008)
12. Feng, Y.-Q., Kwak, J.H., Zhou, C.X.: Constructing even radius tightly attached half-arc-transitive graphs of valency four. J. Algebr. Comb. 26, 431-451 (2007)
13. Feng, Y.-Q., Wang, K.S., Zhou, C.X.: Tetravalent half-transitive graphs of order 4p. Eur. J. Comb. 28, 726-733 (2007)
14. Gorenstein, D.: Finite Simple Groups. Plenum, New York (1982)
15. Holt, D.F.: A graph which is edge transitive but not arc transitive. J. Graph Theory 5, 201-204 (1981)
16. 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)
17. Li, C.H., Lu, Z.P., Zhang, H.: Tetravalent edge-transitive Cayley graphs with odd number of vertices. J. Comb. Theory B 96, 164-181 (2006)
18. Li, C.H., Sim, H.S.: On half-transitive metacirculent graphs of prime-power order. J. Comb. Theory B 81, 45-57 (2001)
19. Malni\check c, A., Maruši\check c, D.: Constructing 4-valent 1 -transitive graphs with a nonsolvable automorphism 2 group. J. Comb. Theory B 75, 46-55 (1999)
20. Malni\check c, A., Maruši\check c, D.: Constructing 1 -arc-transitive graphs of valency 4 and vertex stabilizer 2 Z2 \times Z2. Discrete Math. 245, 203-216 (2002)
21. Maruši\check c, D.: Half-transitive groups actions on finite graphs of valency
4. J. Comb. Theory B 73, 41-76 (1998)
22. Maruši\check c, D., Nedela, R.: Finite graphs of valency 4 and girth 4 admitting half-transitive group actions. J. Aust. Math. Soc. 73, 155-170 (2002)
23. Maruši\check c, D., Nedela, R.: Partial line graph operator and half-arc-transitive group actions. Math. Slovaca 51, 241-257 (2001)
24. Maruši\check c, D., Nedela, R.: Maps and half-transitive graphs of valency
4. Eur. J. Comb. 19, 345-354 (1998)
25. Maruši\check c, D., Praeger, C.E.: Tetravalent graphs admitting half-transitive group action: alternating cycles. J. Comb. Theory B 75, 188-205 (1999)
26. Maruši\check c, D., Šparl, P.: On quartic half-arc-transitive metacirculants. J. Algebr. Comb. 28, 365-395 (2008)
27. Maruši\check c, D., Waller, A.: Half-transitive graphs of valency 4 with prescribed attachment numbers. J. Graph Theory 34, 89-99 (2000)
28. Maruši\check c, D., Xu, M.Y.: A 1 -transitive graph of valency 4 with a nonsolvable group of automorphisms. 2 J. Graph Theory 25, 133-138 (1997)
29. Robinson, D.J.: A Course in the Theory of Groups. Springer, New York (1982)
30. Šparl, P.: A classification of tightly attached half-arc-transitive graphs of valency
4. J. Comb. Theory B 98, 1076-1108 (2008)
31. Tutte, W.: Connectivity in Graphs. University of Toronto Press, Toronto (1966)
32. Taylor, D.E., Xu, M.Y.: Vertex-primitive 1/2-transitive graphs. J. Aust. Math. Soc. A 57, 113-124 (1994)
33. Wang, R.J.: Half-transitive graphs of order a product of two distinct primes. Commun. Algebra 22, 915-927 (1994)
34. Wang, X.Y., Feng, Y.-Q.: There exists no tetravalent half-arc-transitive graph of order 2p2. Discrete Math. 310, 1721-1724 (2010)
35. Wang, X.Y., Feng, Y.-Q.: Hexavalent half-arc-transitive graphs of order 4p. Eur. J. Comb. 30, 1263- 1270 (2009)
36. Wilson, S., Poto\check nik, P.: A Census of edge-transitive tetravalent graphs: Mini-Census, available at
37. Xu, M.Y.: Half-transitive graphs of prime-cube order. J. Algebr. Comb. 1, 275-282 (1992)
38. Zhou, C.X., Feng, Y.-Q.: An infinite family of tetravalent half-arc-transitive graphs. Discrete Math.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition