×

Half-arc-transitive graphs of prime-cube order of small valencies. (English) Zbl 1380.05042

Summary: A graph is called half-arc-transitive if its full automorphism group acts transitively on vertices and edges, but not on arcs. It is well known that for any prime \(p\) there is no half-arc-transitive graph of order \(p\) or \(p^2\). M. Xu [J. Algebr. Comb. 1, No. 3, 275–282 (1992; Zbl 0786.05044)] classified half-arc-transitive graphs of order \(p^3\) and valency 4. In this paper we classify half-arc-transitive graphs of order \(p^3\) and valency 6 or 8. In particular, the first known infinite family of half-arc-transitive Cayley graphs on non-metacyclic \(p\)-groups is constructed.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures

Citations:

Zbl 0786.05044

Software:

Magma
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] B. Alspach, D. Maruˇsiˇc and L. Nowitz, Constructing graphs which are 1/2-transitive, J. Austral. Math. Soc. Ser. A56 (1994), 391-402, doi:10.1023/a:1022466626755. · Zbl 0808.05057
[2] B. Alspach and M. Y. Xu, 1/2-transitive graphs of order 3p, J. Algebraic Combin. 3 (1994), 347-355, doi:10.1023/a:1022466626755. · Zbl 0808.05056
[3] I. Antonˇciˇc and P. ˇSparl, Classification of quartic half-arc-transitive weak metacirculants of girth at most 4, Discrete Math. 339 (2016), 931-945, doi:10.1016/j.disc.2015.10.015. · Zbl 1327.05237
[4] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: the user language, J. Symbolic Comput.24 (1997), 235-265, doi:10.1006/jsco.1996.0125. · Zbl 0898.68039
[5] I. Z. Bouwer, Vertex and edge transitive but not 1-transitive graphs, Canad. Math. Bull. 13 (1970), 231-237, doi:10.4153/cmb-1970-047-8. · Zbl 0205.54601
[6] Y. Cheng and J. Oxley, On weakly symmetric graphs of order twice a prime, J. Combin. Theory Ser. B42 (1987), 196-211, doi:10.1016/0095-8956(87)90040-2. · Zbl 0583.05032
[7] M. D. E. Conder and D. Maruˇsiˇc, A tetravalent half-arc-transitive graph with non-abelian vertex stabilizer, J. Combin. Theory Ser. B 88 (2003), 67-76, doi:10.1016/S0095-8956(02)00036-9. · Zbl 1022.05032
[8] M. D. E. Conder, P. Potoˇcnik and P. ˇSparl, Some recent discoveries about half-arc-transitive graphs, Ars Math. Contemp. 8 (2015), 149-162,http://amc-journal.eu/index. php/amc/article/view/557. · Zbl 1317.05190
[9] E. Dobson, Automorphism groups of metacirculant graphs of order a product of two distinct primes, Combin. Probab. Comput. 15 (2006), 105-130, doi:10.1017/S0963548305007066. · Zbl 1082.05048
[10] Y.-Q. Feng, J. H. Kwak, X. Wang and J.-X. Zhou, Tetravalent half-arc-transitive graphs of order p4, European J. Combin. 29 (2008), 555-567, doi:10.1016/j.ejc.2007.05.004. · Zbl 1159.05024
[11] Y.-Q. Feng, J. H. Kwak, X. Wang and J.-X. Zhou, Tetravalent half-arc-transitive graphs of order 2pq, J. Algebraic Combin. 33 (2011), 543-553, doi:10.1007/s10801-010-0257-1. · Zbl 1226.05134
[12] C. D. Godsil, On the full automorphism group of a graph, Combinatorica 1 (1981), 243-256, doi:10.1007/bf02579330. · Zbl 0489.05028
[13] A. Hujdurovi´c, K. Kutnar and D. Maruˇsiˇc, Half-arc-transitive group actions with a small number of alternets, J. Combin. Theory Ser. A 124 (2014), 114-129, doi:10.1016/j.jcta.2014.01.005. · Zbl 1283.05126
[14] B. Huppert, Endliche Gruppen. I, Die Grundlehren der Mathematischen Wissenschaften, Band 134, Springer-Verlag, Berlin-New York, 1967, doi:10.1007/978-3-642-64981-3. · Zbl 0217.07201
[15] K. Kutnar, D. Maruˇsiˇc and P. ˇSparl, An infinite family of half-arc-transitive graphs with universal reachability relation, European J. Combin. 31 (2010), 1725-1734, doi:10.1016/j.ejc.2010. 03.006. · Zbl 1221.05200
[16] K. Kutnar, D. Maruˇsiˇc, P. ˇSparl, R.-J. Wang and M.-Y. Xu, Classification of half-arc-transitive graphs of order 4p, European J. Combin. 34 (2013), 1158-1176, doi:10.1016/j.ejc.2013.04. 004. · Zbl 1292.05134
[17] C. H. Li, On isomorphisms of connected Cayley graphs, Discrete Math. 178 (1998), 109-122, doi:10.1016/s0012-365x(97)81821-3. · Zbl 0886.05078
[18] C. H. Li and H.-S. Sim, On half-transitive metacirculant graphs of prime-power order, J. Combin. Theory Ser. B81 (2001), 45-57, doi:10.1006/jctb.2000.1992. · Zbl 1024.05038
[19] D. Maruˇsiˇc, Vertex transitive graphs and digraphs of order pk, in: Cycles in graphs (Burnaby, B.C., 1982), North-Holland, Amsterdam, volume 115 of North-Holland Math. Stud., pp. 115- 128, 1985, doi:10.1016/s0304-0208(08)73001-9. · Zbl 0571.05024
[20] D. Maruˇsiˇc, Half-transitive group actions on finite graphs of valency 4, J. Combin. Theory Ser. B73 (1998), 41-76, doi:10.1006/jctb.1997.1807. · Zbl 0924.05034
[21] D. Maruˇsiˇc, Quartic half-arc-transitive graphs with large vertex stabilizers, Discrete Math. 299 (2005), 180-193, doi:10.1016/j.disc.2004.02.025. · Zbl 1073.05036
[22] D. Maruˇsiˇc and P. ˇSparl, On quartic half-arc-transitive metacirculants, J. Algebraic Combin. 28 (2008), 365-395, doi:10.1007/s10801-007-0107-y. · Zbl 1160.05032
[23] P. Potoˇcnik, P. Spiga and G. Verret, A census of 4-valent half-arc-transitive graphs and arc-transitive digraphs of valence two, Ars Math. Contemp. 8 (2015), 133-148,http: //amc-journal.eu/index.php/amc/article/view/559. · Zbl 1317.05191
[24] D. J. S. Robinson, A Course in the Theory of Groups, volume 80 of Graduate Texts in Mathematics, Springer-Verlag, New York, 2nd edition, 1996, doi:10.1007/978-1-4419-8594-1.
[25] P. Spiga, Constructing half-arc-transitive graphs of valency four with prescribed vertex stabilizers, Graphs Combin. 32 (2016), 2135-2144, doi:10.1007/s00373-016-1678-y. · Zbl 1349.05168
[26] W. T. Tutte, Connectivity in Graphs, Mathematical Expositions, No. 15, University of Toronto Press, Toronto, Ont.; Oxford University Press, London, 1966. · Zbl 0146.45603
[27] P. ˇSparl, A classification of tightly attached half-arc-transitive graphs of valency 4, J. Combin. Theory Ser. B98 (2008), 1076-1108, doi:10.1016/j.jctb.2008.01.001. · Zbl 1158.05030
[28] P. ˇSparl, On the classification of quartic half-arc-transitive metacirculants, Discrete Math. 309 (2009), 2271-2283, doi:10.1016/j.disc.2008.05.006. · Zbl 1208.05045
[29] Y. Wang and Y.-Q. Feng, Half-arc-transitive graphs of prime-cube order of small valencies, 2016,arXiv:1605.08123[math.CO].
[30] Y. Wang, Y.-Q. Feng and J.-X. Zhou, Cayley digraphs of 2-genetic groups of odd prime-power order, J. Combin. Theory Ser. A 143 (2016), 88-106, doi:10.1016/j.jcta.2016.05.001. · Zbl 1342.05067
[31] M.-Y. Xu, Half-transitive graphs of prime-cube order, J. Algebraic Combin. 1 (1992), 275-282, doi:10.1023/a:1022440002282. · Zbl 0786.05044
[32] M.-Y. Xu, Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math. 182 (1998), 309-319, doi:10.1016/s0012-365x(97)00152-0. · Zbl 0887.05025
[33] J.-X. Zhou, Tetravalent half-arc-transitive p-graphs, J. Algebraic Combin. 44 (2016), 947-971, doi:10.1007/s10801-016-0696-4. · Zbl 1352.05088
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.