×

zbMATH — the first resource for mathematics

Edge-transitive graphs of small order and the answer to a 1967 question by Folkman. (English) Zbl 1428.05326
Summary: 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 question of J. Folkman [J. Comb. Theory 3, 215–232 (1967; Zbl 0158.42501)] 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.
MSC:
05E18 Group actions on combinatorial structures
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures
20C30 Representations of finite symmetric groups
Software:
Magma
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Benson, C. T., On the structure of generalized quadrangles, J. Algebra, 15, 443-454 (1970) · Zbl 0212.52304
[2] Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system. I. The user language, J. Symbolic Comput., 24, 235-265 (1997) · Zbl 0898.68039
[3] Conder, M., Trivalent (cubic) symmetric graphs on up to 10000 vertices
[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., 23, 255-294 (2006) · Zbl 1089.05032
[5] Conder, M.; Verret, G., All connected edge-transitive bipartite graphs on up to 63 vertices
[6] Conder, M.; Verret, G., All connected edge-transitive graphs on up to 47 vertices
[7] Djoković, D.; Miller, G. L., Regular groups of automorphisms of cubic graphs, J. Combin. Theory Ser. B, 29, 195-230 (1980) · Zbl 0385.05040
[8] Du, S.; Xu, M., A classification of semisymmetric graphs of order \(2pq\), Comm. Algebra, 28, 2685-2715 (2000) · Zbl 0944.05051
[9] Folkman, J., Regular line-symmetric graphs, J. Combinatorial Theory, 3, 215-232 (1967) · Zbl 0158.42501
[10] Goldschmidt, D. M., Automorphisms of trivalent graphs, Ann. of Math. (2), 111, 377-406 (1980) · Zbl 0475.05043
[11] Holt, D.; Royle, G., A census of small transitive groups and vertex-transitive graphs
[12] Ivanov, A. V., Combinatorial design theory, 149, On edge but not vertex transitive regular graphs, 273-285 (1987), North-Holland: North-Holland, Amsterdam · Zbl 0629.05040
[13] Kotlov, A.; Lovász, L., The rank and size of graphs, J. Graph Theory, 23, 185-189 (1996) · Zbl 0858.05060
[14] Newman, H. A.; Miranda, H.; Narayan, D. A., Edge-transitive graphs
[15] Potočnik, P.; Spiga, P.; Verret, G., Cubic vertex-transitive graphs on up to 1280 vertices, J. Symbolic Comput., 50, 465-477 (2013) · 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., 8, 133-148 (2015) · Zbl 1317.05191
[17] Royle, G., Vertex-transitive graphs on up to 31 vertices
[18] Royle, G., There are 677402 vertex-transitive graphs on 32 vertices
[19] Wilson, S., A worthy family of semisymmetric graphs, Discrete Math., 271, 283-294 (2003) · Zbl 1021.05048
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.