A census of semisymmetric cubic graphs on up to 768 vertices
Marston Conder1
, Aleksander Malnič2
, Dragan Marušič2
and Primož Potočnik4
1University of Auckland Department of Mathematics Private Bag 92019 Auckland New Zealand
2Univerza v Ljubljani IMFM, Oddelek za matematiko Jadranska 19 1111 Ljubljana Slovenija
4University of Primorska Cankarjeva 5 6000 Koper Slovenia
2Univerza v Ljubljani IMFM, Oddelek za matematiko Jadranska 19 1111 Ljubljana Slovenija
4University of Primorska Cankarjeva 5 6000 Koper Slovenia
DOI: 10.1007/s10801-006-7397-3
Abstract
A list is given of all semisymmetric (edge- but not vertex-transitive) connected finite cubic graphs of order up to 768. This list was determined by the authors using Goldschmidt's classification of finite primitive amalgams of index (3,3), and a computer algorithm for finding all normal subgroups of up to a given index in a finitely-presented group. The list includes several previously undiscovered graphs. For each graph in the list, a significant amount of information is provided, including its girth and diameter, the order of its automorphism group, the order and structure of a minimal edge-transitive group of automorphisms, its Goldschmidt type, stabiliser partitions, and other details about its quotients and covers. A summary of all known infinite families of semisymmetric cubic graphs is also given, together with explicit rules for their construction, and members of the list are identified with these. The special case of those graphs having K 1,3 as a normal quotient is investigated in detail.
Pages: 255–294
Keywords: keywords semisymmetric graphs; edge-transitive graphs; amalgams
Full Text: PDF
References
1. W. Bosma, C. Cannon, and C. Playoust, “The MAGMA algebra system I: The user language,” J. Symbolic Comput. 24 (1997), 235-265.
2. I.Z. Bouwer, “An edge but not vertex transitive cubic graph,” Bull. Can. Math. Soc. 11 (1968), 533-535.
3. I.Z. Bouwer, “On edge but not vertex transitive regular graphs,” J. Combin. Theory, B 12 (1972), 32-40.
4. I.Z. Bouwer (ed.), The Foster Census, Charles Babbage Research Centre, Winnipeg, 1988.
5. M.D.E. Conder and P. Lorimer, “Automorphism Groups of Symmetric Graphs of Valency 3,” J. Combin. Theory, Series B 47 (1989), 60-72.
6. M.D.E. Conder, P. Dobcsányi, B. Mc Kay and G. Royle, The Extended Foster Census,
2. I.Z. Bouwer, “An edge but not vertex transitive cubic graph,” Bull. Can. Math. Soc. 11 (1968), 533-535.
3. I.Z. Bouwer, “On edge but not vertex transitive regular graphs,” J. Combin. Theory, B 12 (1972), 32-40.
4. I.Z. Bouwer (ed.), The Foster Census, Charles Babbage Research Centre, Winnipeg, 1988.
5. M.D.E. Conder and P. Lorimer, “Automorphism Groups of Symmetric Graphs of Valency 3,” J. Combin. Theory, Series B 47 (1989), 60-72.
6. M.D.E. Conder, P. Dobcsányi, B. Mc Kay and G. Royle, The Extended Foster Census,