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$.

Accepted:

Revised after acceptance:

Published online:

DOI: 10.5802/alco.82

Keywords: arc-transitive graph, edge-transitive graph, semi-symmetric graph, twin-free graph

^{1}; Verret, Gabriel

^{1}

@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}, pages = {1275--1284}, publisher = {MathOA foundation}, volume = {2}, number = {6}, year = {2019}, doi = {10.5802/alco.82}, zbl = {1428.05326}, mrnumber = {4049846}, language = {en}, url = {https://alco.centre-mersenne.org/articles/10.5802/alco.82/} }

TY - JOUR AU - Conder, Marston D. E. AU - Verret, Gabriel TI - Edge-transitive graphs of small order and the answer to a 1967 question by Folkman JO - Algebraic Combinatorics PY - 2019 SP - 1275 EP - 1284 VL - 2 IS - 6 PB - MathOA foundation UR - https://alco.centre-mersenne.org/articles/10.5802/alco.82/ DO - 10.5802/alco.82 LA - en ID - ALCO_2019__2_6_1275_0 ER -

%0 Journal Article %A Conder, Marston D. E. %A Verret, Gabriel %T Edge-transitive graphs of small order and the answer to a 1967 question by Folkman %J Algebraic Combinatorics %D 2019 %P 1275-1284 %V 2 %N 6 %I MathOA foundation %U https://alco.centre-mersenne.org/articles/10.5802/alco.82/ %R 10.5802/alco.82 %G en %F 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/articles/10.5802/alco.82/

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

[2] The Magma algebra system. I. The user language, J. Symbolic Comput., Volume 24 (1997), pp. 235-265 Computational algebra and number theory (London, 1993) | DOI | MR | Zbl

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

[4] A census of semisymmetric cubic graphs on up to 768 vertices, J. Algebraic Combin., Volume 23 (2006), pp. 255-294 | DOI | MR | Zbl

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

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

[7] Regular groups of automorphisms of cubic graphs, J. Combin. Theory Ser. B, Volume 29 (1980), pp. 195-230 | DOI | MR

[8] A classification of semisymmetric graphs of order $2pq$, Comm. Algebra, Volume 28 (2000), pp. 2685-2715 | DOI | MR | Zbl

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

[10] Automorphisms of trivalent graphs, Ann. of Math. (2), Volume 111 (1980), pp. 377-406 | DOI | MR | Zbl

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

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

[13] The rank and size of graphs, J. Graph Theory, Volume 23 (1996), pp. 185-189 | DOI | MR | Zbl

[14] Edge-transitive graphs (preprint, https://arxiv.org/abs/1709.04750v1)

[15] Cubic vertex-transitive graphs on up to 1280 vertices, J. Symbolic Comput., Volume 50 (2013), pp. 465-477 | DOI | MR | Zbl

[16] 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 | DOI | MR | Zbl

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

[18] 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] A worthy family of semisymmetric graphs, Discrete Math., Volume 271 (2003), pp. 283-294 | DOI | MR | Zbl

*Cited by Sources: *