×

The smallest symmetric cubic graphs with given type. (English) Zbl 1459.05349

This paper concerns highly symmetric cubic graphs. The basic setup is as follows: we say that a graph is symmetric if its automorphism group acts transitively on pairs consisting of a vertex and an incident edge. This paper is devoted to symmetric finite cubic graphs, for which there exists a good structure theory: given such a graph, its automorphism group is known to act regularly on \(k\)-arcs for some \(1\leqslant k\leqslant5\). This naturally divides the set of symmetric cubic graphs into five types. The types for \(k=2,4\) are further subdivided according to the action of an edge-stabiliser. So there are seven classes, labelled \(1\), \(2^1\), \(2^2\), \(3\), \(4^1\), \(4^2\), \(5\). In [M. Conder and R. Nedela, J. Algebra 322, No. 3, 722–740 (2009; Zbl 1183.05034)], the classes are further subdivided according to the existence of subgroups of the automorphism group which act in each of these seven ways. They showed that there are seventeen possible action types (each of which corresponds to a non-empty subset of \(\{1, 2^1, 2^2, 3, 4^1, 4^2, 5\}\)). They found an example of a graph with each action type, and in fourteen of the cases showed that their example is the smallest. The object of the paper under review is to find the smallest example for each of the other three action types.
The method is via computational group theory: it is known that for each of the seven basic types there is a finitely-presented group which is universal in the sense that the automorphism group of any finite cubic graph of that type is a quotient. So the object is to find suitable quotients of these groups. This is done efficiently using MAGMA.
The paper is well written, but should not be used as an introduction to the subject; it should be read as a sequel to [loc. cit.].

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

Citations:

Zbl 1183.05034

Software:

Magma
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bosma, W.; Cannon, J.; Playoust, C., The magma algebra system I: the user language, J. Symb. Comput., 24, 235-265 (1997) · Zbl 0898.68039
[2] (Bouwer, I. Z., The Foster Census (1988), Charles Babbage Research Centre: Charles Babbage Research Centre Winnipeg) · Zbl 0639.05043
[3] Conder, M. D.E., A new 5-arc-transitive cubic graph, J. Graph Theory, 11, 303-307 (1987) · Zbl 0652.05024
[4] Conder, M. D.E., Trivalent (cubic) symmetric graphs on up to 10000 vertices
[5] Conder, M. D.E.; Dobcsányi, P., Trivalent symmetric graphs on up to 768 vertices, J. Comb. Math. Comb. Comput., 40, 41-63 (2002) · Zbl 0996.05069
[6] Conder, M. D.E.; Lorimer, P. J., Automorphism groups of symmetric graphs of valency 3, J. Comb. Theory, Ser. B, 47, 60-72 (1989) · Zbl 0682.05036
[7] Conder, M.; Nedela, R., A refined classification of symmetric cubic graphs, J. Algebra, 322, 722-740 (2009) · Zbl 1183.05034
[8] Conway, J. H.; Curtis, R. T.; Norton, S. P.; Parker, R. A.; Wilson, R. A., An Atlas of Finite Groups (1985), Oxford University Press: Oxford University Press London · Zbl 0568.20001
[9] Djoković, D.Ž.; Miller, G. L., Regular groups of automorphisms of cubic graphs, J. Comb. Theory, Ser. B, 29, 195-230 (1980) · Zbl 0385.05040
[10] Robinson, D. J.S., A Course in the Theory of Groups (1996), Springer
[11] Tutte, W. T., A family of cubical graphs, Proc. Camb. Philos. Soc., 43, 459-474 (1947) · Zbl 0029.42401
[12] Tutte, W. T., On the symmetry of cubic graphs, Can. J. Math., 11, 621-624 (1959) · Zbl 0093.37701
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.