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 2p 2 exist and a tetravalent half-arc-transitive graph of order 4p 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 2pq are classified for distinct odd primes p and q.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alspach, B., Marušič, D., Nowitz, L.: Constructing graphs which are 1/2-transitive. J. Aust. Math. Soc. A 56, 391–402 (1994)
Alspach, B., Xu, M.Y.: 1/2-transitive graphs of order 3p. J. Algebr. Comb. 1, 275–282 (1992)
Babai, L.: Isomorphism problem for a class of point-symmetric structures. Acta Math. Acad. Sci. Hung. 29, 329–336 (1977)
Biggs, N.: Algebraic Graph Theory, 2nd edn. Cambridge University Press, Cambridge (1993)
Bouwer, I.Z.: Vertex- and edge-transitive but not 1-transitive graphs. Can. Math. Bull. 13, 231–237 (1970)
Chao, C.Y.: On the classification of symmetric graphs with a prime number of vertices. Trans. Am. Math. Soc. 158, 247–256 (1971)
Cheng, Y., Oxley, J.: On weakly symmetric graphs of order twice a prime. J. Comb. Theory B 42, 196–211 (1987)
Conder, M.D.E., Marušič, D.: A tetravalent half-arc-transitive graph with non-abelian vertex stabilizer. J. Comb. Theory B 88, 67–76 (2003)
Du, S.F., Xu, M.Y.: Vertex-primitive \(\frac{1}{2}\)-arc-transitive graphs of smallest order. Commun. Algebra 27, 163–171 (1999)
Fang, X.G., Li, C.H., Xu, M.Y.: On edge-transitive Cayley graphs of valency 4. Eur. J. Comb. 25, 1107–1116 (2004)
Feng, Y.-Q., Kwak, J.H., Xu, M.Y., Zhou, J.-X.: Tetravalent half-arc-transitive graphs of order p 4. Eur. J. Comb. 29, 555–567 (2008)
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)
Feng, Y.-Q., Wang, K.S., Zhou, C.X.: Tetravalent half-transitive graphs of order 4p. Eur. J. Comb. 28, 726–733 (2007)
Gorenstein, D.: Finite Simple Groups. Plenum, New York (1982)
Holt, D.F.: A graph which is edge transitive but not arc transitive. J. Graph Theory 5, 201–204 (1981)
Li, C.H., Lu, Z.P., Marušič, D.: On primitive permutation groups with small suborbits and their orbital graphs. J. Algebra 279, 749–770 (2004)
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)
Li, C.H., Sim, H.S.: On half-transitive metacirculent graphs of prime-power order. J. Comb. Theory B 81, 45–57 (2001)
Malnič, A., Marušič, D.: Constructing 4-valent \(\frac{1}{2}\)-transitive graphs with a nonsolvable automorphism group. J. Comb. Theory B 75, 46–55 (1999)
Malnič, A., Marušič, D.: Constructing \(\frac{1}{2}\)-arc-transitive graphs of valency 4 and vertex stabilizer ℤ2×ℤ2. Discrete Math. 245, 203–216 (2002)
Marušič, D.: Half-transitive groups actions on finite graphs of valency 4. J. Comb. Theory B 73, 41–76 (1998)
Marušič, D., Nedela, R.: Finite graphs of valency 4 and girth 4 admitting half-transitive group actions. J. Aust. Math. Soc. 73, 155–170 (2002)
Marušič, D., Nedela, R.: Partial line graph operator and half-arc-transitive group actions. Math. Slovaca 51, 241–257 (2001)
Marušič, D., Nedela, R.: Maps and half-transitive graphs of valency 4. Eur. J. Comb. 19, 345–354 (1998)
Marušič, D., Praeger, C.E.: Tetravalent graphs admitting half-transitive group action: alternating cycles. J. Comb. Theory B 75, 188–205 (1999)
Marušič, D., Šparl, P.: On quartic half-arc-transitive metacirculants. J. Algebr. Comb. 28, 365–395 (2008)
Marušič, D., Waller, A.: Half-transitive graphs of valency 4 with prescribed attachment numbers. J. Graph Theory 34, 89–99 (2000)
Marušič, D., Xu, M.Y.: A \(\frac{1}{2}\)-transitive graph of valency 4 with a nonsolvable group of automorphisms. J. Graph Theory 25, 133–138 (1997)
Robinson, D.J.: A Course in the Theory of Groups. Springer, New York (1982)
Šparl, P.: A classification of tightly attached half-arc-transitive graphs of valency 4. J. Comb. Theory B 98, 1076–1108 (2008)
Tutte, W.: Connectivity in Graphs. University of Toronto Press, Toronto (1966)
Taylor, D.E., Xu, M.Y.: Vertex-primitive 1/2-transitive graphs. J. Aust. Math. Soc. A 57, 113–124 (1994)
Wang, R.J.: Half-transitive graphs of order a product of two distinct primes. Commun. Algebra 22, 915–927 (1994)
Wang, X.Y., Feng, Y.-Q.: There exists no tetravalent half-arc-transitive graph of order 2p 2. Discrete Math. 310, 1721–1724 (2010)
Wang, X.Y., Feng, Y.-Q.: Hexavalent half-arc-transitive graphs of order 4p. Eur. J. Comb. 30, 1263–1270 (2009)
Wilson, S., Potoňik, P.: A Census of edge-transitive tetravalent graphs: Mini-Census, available at http://jan.ucc.nau.edu/swilson/C4Site/index.html
Xu, M.Y.: Half-transitive graphs of prime-cube order. J. Algebr. Comb. 1, 275–282 (1992)
Zhou, C.X., Feng, Y.-Q.: An infinite family of tetravalent half-arc-transitive graphs. Discrete Math. 306, 2205–2211 (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Feng, YQ., Kwak, J.H., Wang, X. et al. Tetravalent half-arc-transitive graphs of order 2pq . J Algebr Comb 33, 543–553 (2011). https://doi.org/10.1007/s10801-010-0257-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10801-010-0257-1