JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 26, No 4 (2007)

Yan-Quan Feng¹ , Jin Ho Kwak² and Chuixiang Zhou¹

¹Beijing Jiaotong University Department of Mathematics Beijing 100044 People's Republic of China
²Pohang University of Science and Technology Department of Mathematics Pohang 790-784 Korea

A finite graph X is half-arc-transitive if its automorphism group is transitive on vertices and edges, but not on arcs. When X is tetravalent, the automorphism group induces an orientation on the edges and a cycle of X is called an alternating cycle if its consecutive edges in the cycle have opposite orientations. All alternating cycles of X have the same length and half of this length is called the radius of X. The graph X is said to be tightly attached if any two adjacent alternating cycles intersect in the same number of vertices equal to the radius of  X. Marušič ( J. Comb. Theory B, 73, 41-76, 1998) classified odd radius tightly attached tetravalent half-arc-transitive graphs. In this paper, we classify the half-arc-transitive regular coverings of the complete bipartite graph K _4,4 whose covering transformation group is cyclic of prime-power order and whose fibre-preserving group contains a half-arc-transitive subgroup. As a result, two new infinite families of even radius tightly attached tetravalent half-arc-transitive graphs are constructed, introducing the first infinite families of tetravalent half-arc-transitive graphs of 2-power orders.

1. Alspach, B., & Xu, M. Y. (1992). 1/2-transitive graphs of order 3p. J. Algebr. Comb., 1, 275-282.
2. Alspach, B., Maruši\check c, D., & Nowitz, L. (1994). Constructing graphs which are 1/2-transitive. J. Aust. Math. Soc. A, 56, 391-402.
3. Bosma, W., Cannon, C., & Playoust, C. (1997). The MAGMA algebra system I The user language. J. Symb. Comput., 24, 235-265.
4. Bouwer, I. Z. (1970). Vertex and edge-transitive but not 1-transitive graphs. Canad. Math. Bull., 13, 231-237.
5. Conder, M. D. E., & Maruši\check c, D. (2003). A tetravalent half-arc-transitive graph with non-abelian vertex stabilizer. J. Comb. Theory B, 88, 67-76.
6. D'Azevedo, A. B., & Nedela, R. (2004). Half-arc-transitive graphs and chiral hypermaps. Eur. J. Comb., 25, 423-436.
7. Djoković, D. Z. (1974). Automorphisms of graphs and coverings. J. Comb. Theory B, 16, 243-247.
8. Du, S. F., & Xu, M. Y. (1999). Vertex-primitive 1 -arc-transitive graphs of smallest order. Comm. 2 Algebra, 27, 163-171.
9. Fang, X. G., Li, C. H., & Xu, M. Y. (2004). On edge-transitive Cayley graphs of valency four. Eur. J. Comb., 25, 1107-1116.
10. Feng, Y.-Q., & Kwak, J. H. (2004). s-Regular cubic graphs as coverings of the complete bipartite graph K3,3. J. Graph Theory, 45, 101-112.
11. Feng, Y.-Q., & Wang, K. S. (2003). s-Regular cubic graphs as coverings of the three dimensional hypercube Q3. Eur. J. Comb., 24, 719-731.
12. Feng, Y.-Q., Kwak, J. H., & Wang, K. S. (2005). Classifying cubic symmetric graphs of order 8p or 8p2. Eur. J. Comb., 26, 1033-1052.
13. Feng, Y.-Q., Wang, K. S., & Zhou, C. X. (2007). Tetravalent half-transitive graphs of order 4p. Eur. J. Comb., 28, 726-733.
14. Gross, J. L., & Tucker, T. W. (1977). Generating all graph coverings by permutation voltage assignment. Discrete Math., 18, 273-283.
15. Holt, D. F. (1981). A graph which is edge transitive but not arc transitive. J. Graph Theory, 5, 201- 204.
16. Hong, S., Kwak, J. H., & Lee, J. (1996). Regular graph coverings whose covering transformation groups have the isomorphism extension property. Discrete Math., 168, 85-105.
17. Li, C. H., & Sim, H. S. (2001). On half-transitive metacirculant graphs of prime-power order. J. Comb. Theory B, 81, 45-57.
18. Li, C. H., Lu, Z. P., & Maruši\check c, D. (2004). On primitive permutation groups with small suborbits and their orbital graphs. J. Algebra, 279, 749-770.
19. Li, C. H., Lu, Z. P., & Zhang, H. (2006). Tetravalent edge-transitive graphs with odd number of vertices. J. Comb. Theory B, 96, 164-181.
20. Malni\check c, A. (1998). Group actions, coverings and lifts of automorphisms. Discrete Math., 182, 203- 218.
21. Malni\check c, A., & Maruši\check c, D. (1993). Imprimitive graphs and graph coverings. In D. Jungnickel, S. A. Vanstone (Eds.). Coding theory, design theory, group theory, Proceedings of M. Hall memorial conference (pp. 221-229). New York: Wiley
22. Malni\check c, A., & Maruši\check c, D. (1999). Constructing 4-valent 1 -transitive graphs with a nonsolvable au- 2 tomorphism group. J. Comb. Theory B, 75, 46-55.
23. Malni\check c, A., & Maruši\check c, D. (2002). Constructing 1 -arc-transitive graphs of valency 4 and vertex sta- 2 bilizer Z2 \times Z2. Discrete Math., 245, 203-216.
24. Malni\check c, A., & Poto\check cnik, P. (2006). Invariant subspaces, duality, and covers of the Petersen graph. Eur. J. Comb., 27, 971-989.
25. Malni\check c, A., Maruši\check c, D., & Poto\check cnik, P. (2004). On cubic graphs admitting an edge-transitive solvable group. J. Algebr. Comb., 20, 99-113.
26. Malni\check c, A., Maruši\check c, D., & Poto\check cnik, P. (2004). Elementary abelian covers of graphs. J. Algebr. Comb., 20, 71-97.
27. Malni\check c, A., Maruši\check c, D., Poto\check cnik, P., & Wang, C. Q. (2004). An infinite family of cubic edgebut not vertex-transitive graphs. Discrete Math., 280, 133-148.
28. Malni\check c, A., Nedela, R., & Škoviera, M. (2000). Lifting graph automorphisms by voltage assignments. Eur. J. Comb., 21, 927-947.
29. Maruši\check c, D. (1998). Half-transitive group actions on finite graphs of valency
4. J. Comb. Theory B, 73, 41-76.
30. Maruši\check c, D. (1998). Recent developments in half-transitive graphs. Discrete Math., 182, 219-231.
31. Maruši\check c, D. (2005). Quartic half-arc-transitive graphs with large vertex stabilizers. Discrete Math., 299, 180-193.
32. Maruši\check c, D., & Nedela, R. (1998). Maps and half-transitive graphs of valency
4. Eur. J. Comb., 19, 345-354.
33. Maruši\check c, D., & Nedela, R. (2001). Partial line graph operator and half-arc-transitive group actions. Math. Slovaca, 51, 241-257.
34. Maruši\check c, D., & Nedela, R. (2001). On the point stabilizers of transitive groups with non-self-paired suborbits of length
2. J. Group Theory, 4, 19-43.
35. Maruši\check c, D., & Nedela, R. (2002). Finite graphs of valency 4 and girth 4 admitting half-transitive group actions. J. Aust. Math. Soc., 73, 155-170.
36. Maruši\check c, D., & Pisanski, T. (1999). Weakly flag-transitive configurations and 1 -transitive graphs. Eur. 2 J. Comb., 20, 559-570.
37. Maruši\check c, D., & Praeger, C. E. (1999). Tetravalent graphs admitting half-transitive group actions alternating cycles. J. Comb. Theory B, 75, 185-205.
38. Maruši\check c, D., & Waller, A. (2000). Half-transitive graphs of valency 4 with prescribed attachment numbers. J. Graph Theory, 34, 89-99.
39. Maruši\check c, D., & Xu, M. Y. (1997). A 1 -transitive graph of valency 4 with a nonsolvable group of 2 automorphisms. J. Graph Theory, 25, 133-138.
40. Šajna, M. (1998). Half-transitivity of some metacirculants. Discrete Math., 185, 117-136.
41. Škoviera, M. (1986). A contribution to the theory of voltage graphs. Discrete Math., 61, 281-292.
42. Taylor, D. E., & Xu, M. Y. (1994). Vertex-primitive 1 -transitive graphs. J. Aust. Math. Soc. Ser. A, 2 57, 113-124.
43. Tutte, W. T. (1966). Connectivity in graphs. Toronto: University of Toronto Press.
44. Wang, R. J. (1994). Half-transitive graphs of order a product of two distinct primes. Commun. Algebra, 22, 915-927.
45. Wilson, S. (2004). Semi-transitive graphs. J. Graph Theory, 45, 1-27.
46. Xu, M. Y. (1992). Half-transitive graphs of prime-cube order. J. Algebr. Comb., 1, 275-282.
47. Zhou, C. X., & Feng, Y.-Q. (2006). An infinite family of tetravalent half-arc-transitive graphs. Discrete Math., 306, 2205-2211.