Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alspach, B., & Xu, M. Y. (1992). 1/2-transitive graphs of order 3p. J. Algebr. Comb., 1, 275–282.
Alspach, B., Marušič, D., & Nowitz, L. (1994). Constructing graphs which are 1/2-transitive. J. Aust. Math. Soc. A, 56, 391–402.
Bosma, W., Cannon, C., & Playoust, C. (1997). The MAGMA algebra system I The user language. J. Symb. Comput., 24, 235–265.
Bouwer, I. Z. (1970). Vertex and edge-transitive but not 1-transitive graphs. Canad. Math. Bull., 13, 231–237.
Conder, M. D. E., & Marušič, D. (2003). A tetravalent half-arc-transitive graph with non-abelian vertex stabilizer. J. Comb. Theory B, 88, 67–76.
D’Azevedo, A. B., & Nedela, R. (2004). Half-arc-transitive graphs and chiral hypermaps. Eur. J. Comb., 25, 423–436.
Djoković, D. Z. (1974). Automorphisms of graphs and coverings. J. Comb. Theory B, 16, 243–247.
Du, S. F., & Xu, M. Y. (1999). Vertex-primitive \(\frac{1}{2}\) -arc-transitive graphs of smallest order. Comm. Algebra, 27, 163–171.
Fang, X. G., Li, C. H., & Xu, M. Y. (2004). On edge-transitive Cayley graphs of valency four. Eur. J. Comb., 25, 1107–1116.
Feng, Y.-Q., & Kwak, J. H. (2004). s-Regular cubic graphs as coverings of the complete bipartite graph K 3,3. J. Graph Theory, 45, 101–112.
Feng, Y.-Q., & Wang, K. S. (2003). s-Regular cubic graphs as coverings of the three dimensional hypercube Q 3. Eur. J. Comb., 24, 719–731.
Feng, Y.-Q., Kwak, J. H., & Wang, K. S. (2005). Classifying cubic symmetric graphs of order 8p or 8p 2. Eur. J. Comb., 26, 1033–1052.
Feng, Y.-Q., Wang, K. S., & Zhou, C. X. (2007). Tetravalent half-transitive graphs of order 4p. Eur. J. Comb., 28, 726–733.
Gross, J. L., & Tucker, T. W. (1977). Generating all graph coverings by permutation voltage assignment. Discrete Math., 18, 273–283.
Holt, D. F. (1981). A graph which is edge transitive but not arc transitive. J. Graph Theory, 5, 201–204.
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.
Li, C. H., & Sim, H. S. (2001). On half-transitive metacirculant graphs of prime-power order. J. Comb. Theory B, 81, 45–57.
Li, C. H., Lu, Z. P., & Marušič, D. (2004). On primitive permutation groups with small suborbits and their orbital graphs. J. Algebra, 279, 749–770.
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.
Malnič, A. (1998). Group actions, coverings and lifts of automorphisms. Discrete Math., 182, 203–218.
Malnič, A., & Marušič, 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
Malnič, A., & Marušič, D. (1999). Constructing 4-valent \(\frac{1}{2}\) -transitive graphs with a nonsolvable automorphism group. J. Comb. Theory B, 75, 46–55.
Malnič, A., & Marušič, D. (2002). Constructing \(\frac{1}{2}\) -arc-transitive graphs of valency 4 and vertex stabilizer ℤ2×ℤ2. Discrete Math., 245, 203–216.
Malnič, A., & Potočnik, P. (2006). Invariant subspaces, duality, and covers of the Petersen graph. Eur. J. Comb., 27, 971–989.
Malnič, A., Marušič, D., & Potočnik, P. (2004). On cubic graphs admitting an edge-transitive solvable group. J. Algebr. Comb., 20, 99–113.
Malnič, A., Marušič, D., & Potočnik, P. (2004). Elementary abelian covers of graphs. J. Algebr. Comb., 20, 71–97.
Malnič, A., Marušič, D., Potočnik, P., & Wang, C. Q. (2004). An infinite family of cubic edge- but not vertex-transitive graphs. Discrete Math., 280, 133–148.
Malnič, A., Nedela, R., & Škoviera, M. (2000). Lifting graph automorphisms by voltage assignments. Eur. J. Comb., 21, 927–947.
Marušič, D. (1998). Half-transitive group actions on finite graphs of valency 4. J. Comb. Theory B, 73, 41–76.
Marušič, D. (1998). Recent developments in half-transitive graphs. Discrete Math., 182, 219–231.
Marušič, D. (2005). Quartic half-arc-transitive graphs with large vertex stabilizers. Discrete Math., 299, 180–193.
Marušič, D., & Nedela, R. (1998). Maps and half-transitive graphs of valency 4. Eur. J. Comb., 19, 345–354.
Marušič, D., & Nedela, R. (2001). Partial line graph operator and half-arc-transitive group actions. Math. Slovaca, 51, 241–257.
Marušič, 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.
Marušič, D., & Nedela, R. (2002). Finite graphs of valency 4 and girth 4 admitting half-transitive group actions. J. Aust. Math. Soc., 73, 155–170.
Marušič, D., & Pisanski, T. (1999). Weakly flag-transitive configurations and \(\frac{1}{2}\) -transitive graphs. Eur. J. Comb., 20, 559–570.
Marušič, D., & Praeger, C. E. (1999). Tetravalent graphs admitting half-transitive group actions alternating cycles. J. Comb. Theory B, 75, 185–205.
Marušič, D., & Waller, A. (2000). Half-transitive graphs of valency 4 with prescribed attachment numbers. J. Graph Theory, 34, 89–99.
Marušič, D., & Xu, M. Y. (1997). A \(\frac{1}{2}\) -transitive graph of valency 4 with a nonsolvable group of automorphisms. J. Graph Theory, 25, 133–138.
Šajna, M. (1998). Half-transitivity of some metacirculants. Discrete Math., 185, 117–136.
Škoviera, M. (1986). A contribution to the theory of voltage graphs. Discrete Math., 61, 281–292.
Taylor, D. E., & Xu, M. Y. (1994). Vertex-primitive \(\frac{1}{2}\) -transitive graphs. J. Aust. Math. Soc. Ser. A, 57, 113–124.
Tutte, W. T. (1966). Connectivity in graphs. Toronto: University of Toronto Press.
Wang, R. J. (1994). Half-transitive graphs of order a product of two distinct primes. Commun. Algebra, 22, 915–927.
Wilson, S. (2004). Semi-transitive graphs. J. Graph Theory, 45, 1–27.
Xu, M. Y. (1992). Half-transitive graphs of prime-cube order. J. Algebr. Comb., 1, 275–282.
Zhou, C. X., & Feng, Y.-Q. (2006). An infinite family of tetravalent half-arc-transitive graphs. Discrete Math., 306, 2205–2211.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Feng, YQ., Kwak, J.H. & Zhou, C. Constructing even radius tightly attached half-arc-transitive graphs of valency four. J Algebr Comb 26, 431–451 (2007). https://doi.org/10.1007/s10801-007-0064-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10801-007-0064-5