JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 28, No 3 (2008)

Dragan Marušič¹ and Primož Šparl²

¹University of Primorska FAMNIT Glagolja{s}ka 8 6000 Koper Slovenia
²University of Ljubljana IMFM Jadranska 19 1111 Ljubljana Slovenia

Following Alspach and Parsons, a metacirculant graph is a graph admitting a transitive group generated by two automorphisms ρ  and σ , where ρ  is ( m, n)-semiregular for some integers m\geq 1, n\geq 2, and where σ  normalizes ρ , cyclically permuting the orbits of ρ  in such a way that σ  ^m has at least one fixed vertex. A  half-arc-transitive graph is a vertex- and edge- but not arc-transitive graph. In this article quartic half-arc-transitive metacirculants are explored and their connection to the so called tightly attached quartic half-arc-transitive graphs is explored. It is shown that there are three essentially different possibilities for a quartic half-arc-transitive metacirculant which is not tightly attached to exist. These graphs are extensively studied and some infinite families of such graphs are constructed.

1. Alspach, B., Parsons, T.D.: A construction for vertex-transitive graphs. Can. J. Math. 34, 307-318 (1982)
2. Alspach, B., Xu, M.-Y.: 1 -arc-transitive graphs of order 3p. J. Algebr. Comb. 3, 347-355 (1994) 2
3. Alspach, B., Maruši\check c, D., Nowitz, L.: Constructing graphs which are 1 -transitive. J. Aust. Math. Soc. 2 A 56, 391-402 (1994)
4. Biggs, N., White, A.T.: Permutation Groups and Combinatorial Structures. Cambridge University Press, Cambridge (1979)
5. Bondy, A., Murty, U.S.R.: Graph Theory with Applications. Elsevier, New York (1976)
6. Bouwer, I.Z.: Vertex and edge-transitive but not 1-transitive graphs. Can. Math. Bull. 13, 231-237 (1970)
7. Conder, M.D.E., Maruši\check c, D.: A tetravalent half-arc-transitive graph with nonabelian vertex stabilizer. J. Comb. Theory B 88, 67-76 (2003)
8. D'Azevedo, A.B., Nedela, R.: Half-arc-transitive graphs and chiral hypermaps. Eur. J. Comb. 25, 423-436 (2004)
9. Dixon, J.D., Mortimer, B.: Permutation Groups. Springer, New York (1996)
10. Doyle, P.G.: On transitive graphs. Senior Thesis, Harvard College (1976)
11. Du, S.F., Xu, M.Y.: Vertex-primitive 1 -arc-transitive graphs of smallest order. Commun. Algebra 27, 2 163-171 (1998)
12. Feng, Y.Q., Kwak, J.H., Xu, M.Y., Zhou, J.X.: Tetravalent half-arc-transitive graphs of order p4. Eur. J. Comb. (2007), doi:
13. Feng, Y.Q., Wang, K.S., Zhou, C.X.: Constructing even radius tightly attached half-arc-transitive graphs of valency four. J. Algebr. Comb. 26, 431-451 (2007)
14. Feng, Y.Q., Wang, K.S., Zhou, C.X.: Tetravalent half-transitive graphs of order 4p. Eur. J. Comb. 28, 726-733 (2007)
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., Sims, H.S.: On half-transitive metacirculant graphs of prime-power order. J. Comb. Theory B 81, 45-57 (2001)
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. Malni\check c, A., Maruši\check c, D.: Constructing 4-valent 1 -transitive graphs with a nonsolvable autmorphism 2 group. J. Comb. Theory B 75, 46-55 (1999)
19. Malni\check c, A., Nedela, R., Škoviera, M.: Lifting graph automorphisms by voltage assignments. Eur. J. Comb. 21, 927-947 (2000)
20. Maruši\check c, D.: Half-transitive group actions on finite graphs of valency
4. J. Comb. Theory B 73, 41-76 (1998)
21. Maruši\check c, D.: Recent developments in half-transitive graphs. Discrete Math. 182, 219-231 (1998)
22. Maruši\check c, D.: Quartic half-arc-transitive graphs with large vertex stabilizers. Discrete Math. 299, 180- 193 (2005)
23. Maruši\check c, D., Nedela, R.: Maps and half-transitive graphs of valency
4. Eur. J. Comb. 19, 345-354 (1998)
24. Maruši\check c, D., Nedela, R.: On the point stabilizers of transitive permutation groups with non-self-paired suborbits of length
2. J. Group Theory 4, 19-43 (2001)
25. 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)
26. Maruši\check c, D., Pisanski, T.: Weakly flag-transitive configurations and 1 -transitive graphs. Eur. J. Comb. 2 20, 559-570 (1999)
27. Maruši\check c, D., Praeger, C.E.: Tetravalent graphs admitting half-transitive group actions: alternating cycles. J. Comb. Theory B 75, 188-205 (1999)
28. Maruši\check c, D., Waller, A.O.: Half-transitive graphs of valency 4 with prescribed attachment numbers. J. Graph Theory 34, 89-99 (2000)
29. Šparl, P.: A classification of tightly attached half-arc-transitive graphs of valency 4 (submitted)
30. Taylor, D.E., Xu, M.Y.: Vertex-primitive 1 -transitive graphs. J. Aust. Math. Soc. A 57, 113-124 2 (1994)
31. Thomassen, C., Watkins, M.E.: Infinite vertex-transitive, edge-transitive, non 1-transitive graphs. Proc. Am. Math. Soc. 105, 258-261 (1989)
32. Tutte, W.T.: Connectivity in Graphs. University of Toronto Press, Toronto (1966)
33. Wang, R.J.: Half-transitive graphs of order a product of two distinct primes. Commun. Algebra 22, 915-927 (1994)
34. Wielandt, H.: Finite Permutation Groups. Academic, New York (1964)
35. Wilson, S.: Semi-transitive graphs. J. Graph Theory 45, 1-27 (2004)
36. Xu, M.Y.: Half-transitive graphs of prime cube order. J. Algebr. Comb. 1, 275-282 (1992)
37. Zhou, C.X., Feng, Y.Q.: An infinite family of tetravalent half-arc-transitive graphs. Discrete Math.