ALGEBRAIC COMBINATORICS

Edge-transitive graphs of small order and the answer to a 1967 question by Folkman
Algebraic Combinatorics, Volume 2 (2019) no. 6, p. 1275-1284

In this paper, we introduce a method for finding all edge-transitive graphs of small order, using faithful representations of transitive permutation groups of small degree, and we explain how we used this method to find all edge-transitive graphs of order up to 47, and all bipartite edge-transitive graphs of order up to 63. We also give an answer to a 1967 question of Folkman about semi-symmetric graphs of large valency; in fact we show that for semi-symmetric graphs of order 2n and valency d, the ratio d/n can be arbitrarily close to 1.

Received : 2018-08-20
Accepted : 2019-04-27
Revised after acceptance : 2019-05-29
Published online : 2019-12-04
DOI : https://doi.org/10.5802/alco.82
Classification:  05E18,  05C25,  20B25
Keywords: arc-transitive graph, edge-transitive graph, semi-symmetric graph, twin-free graph 
@article{ALCO_2019__2_6_1275_0,
     author = {Conder, Marston D. E. and Verret, Gabriel},
     title = {Edge-transitive graphs of small order and the answer to a 1967 question by Folkman},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {2},
     number = {6},
     year = {2019},
     pages = {1275-1284},
     doi = {10.5802/alco.82},
     language = {en},
     url = {https://alco.centre-mersenne.org/item/ALCO_2019__2_6_1275_0}
}

Conder, Marston D. E.; Verret, Gabriel. Edge-transitive graphs of small order and the answer to a 1967 question by Folkman. Algebraic Combinatorics, Volume 2 (2019) no. 6, pp. 1275-1284. doi : 10.5802/alco.82. https://alco.centre-mersenne.org/item/ALCO_2019__2_6_1275_0/

[1] Benson, C.T. On the structure of generalized quadrangles, J. Algebra, Volume 15 (1970), pp. 443-454 | Article | MR 289332

[2] Bosma, W.; Cannon, J.; Playoust, C. The Magma algebra system. I. The user language, J. Symbolic Comput., Volume 24 (1997), pp. 235-265 (Computational algebra and number theory (London, 1993)) | Article | MR 1484478 | Zbl 0898.68039

[3] Conder, M. Trivalent (cubic) symmetric graphs on up to 10000 vertices (http://www.math.auckland.ac.nz/~conder/symmcubic10000list.txt)

[4] Conder, M.; Malnič, A.; Marušič, D.; Potočnik, P. A census of semisymmetric cubic graphs on up to 768 vertices, J. Algebraic Combin., Volume 23 (2006), pp. 255-294 | Article | MR 2228929 | Zbl 1089.05032

[5] Conder, M.; Verret, G. All connected edge-transitive bipartite graphs on up to 63 vertices (http://www.math.auckland.ac.nz/~conder/AllSmallETBgraphs-upto63-summary.txt)

[6] Conder, M.; Verret, G. All connected edge-transitive graphs on up to 47 vertices (http://www.math.auckland.ac.nz/~conder/AllSmallETgraphs-upto47-summary.txt)

[7] Djoković, D.; Miller, G.L. Regular groups of automorphisms of cubic graphs, J. Combin. Theory Ser. B, Volume 29 (1980), pp. 195-230 | Article | MR 586434

[8] Du, S.; Xu, M. A classification of semisymmetric graphs of order 2pq, Comm. Algebra, Volume 28 (2000), pp. 2685-2715 | Article | MR 1757424 | Zbl 0944.05051

[9] Folkman, J. Regular line-symmetric graphs, J. Combinatorial Theory, Volume 3 (1967), pp. 215-232 | Article | MR 224498 | Zbl 0158.42501

[10] Goldschmidt, D.M. Automorphisms of trivalent graphs, Ann. of Math. (2), Volume 111 (1980), pp. 377-406 | Article | MR 569075 | Zbl 0475.05043

[11] Holt, D.; Royle, G. A census of small transitive groups and vertex-transitive graphs (https://arxiv.org/abs/1811.09015v1)

[12] Ivanov, A.V. On edge but not vertex transitive regular graphs, Combinatorial design theory (North-Holland Math. Stud.) Volume 149, North-Holland, Amsterdam, 1987, pp. 273-285 | Article | MR 920651 | Zbl 0629.05040

[13] Kotlov, A.; Lovász, L. The rank and size of graphs, J. Graph Theory, Volume 23 (1996), pp. 185-189 | Article | MR 1408346 | Zbl 0858.05060

[14] Newman, H.A.; Miranda, H.; Narayan, D.A. Edge-transitive graphs (preprint, https://arxiv.org/abs/1709.04750v1)

[15] Potočnik, P.; Spiga, P.; Verret, G. Cubic vertex-transitive graphs on up to 1280 vertices, J. Symbolic Comput., Volume 50 (2013), pp. 465-477 | Article | MR 2996891 | Zbl 1256.05102

[16] Potočnik, P.; Spiga, P.; Verret, G. A census of 4-valent half-arc-transitive graphs and arc-transitive digraphs of valence two, Ars Math. Contemp., Volume 8 (2015), pp. 133-148 | Article | MR 3281125 | Zbl 1317.05191

[17] Royle, G. Vertex-transitive graphs on up to 31 vertices (http://staffhome.ecm.uwa.edu.au/~00013890/remote/trans/index.html)

[18] Royle, G. There are 677402 vertex-transitive graphs on 32 vertices (http://symomega.wordpress.com/2012/02/27/there-are-677402-vertex-transitive-graphs-on-32-vertices)

[19] Wilson, S. A worthy family of semisymmetric graphs, Discrete Math., Volume 271 (2003), pp. 283-294 | Article | MR 1999550 | Zbl 1021.05048