کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4657541 | 1343746 | 2007 | 12 صفحه PDF | دانلود رایگان |

A graph Γ is symmetric if its automorphism group acts transitively on the arcs of Γ, and s-regular if its automorphism group acts regularly on the set of s-arcs of Γ. Tutte [W.T. Tutte, A family of cubical graphs, Proc. Cambridge Philos. Soc. 43 (1947) 459–474; W.T. Tutte, On the symmetry of cubic graphs, Canad. J. Math. 11 (1959) 621–624] showed that every cubic finite symmetric cubic graph is s-regular for some s⩽5. We show that a symmetric cubic graph of girth at most 9 is either 1-regular or 2′-regular (following the notation of Djoković), or belongs to a small family of exceptional graphs. On the other hand, we show that there are infinitely many 3-regular cubic graphs of girth 10, so that the statement for girth at most 9 cannot be improved to cubic graphs of larger girth. Also we give a characterisation of the 1- or 2′-regular cubic graphs of girth g⩽9, proving that with five exceptions these are closely related with quotients of the triangle group Δ(2,3,g) in each case, or of the group 〈x,y|x2=y3=4[x,y]=1〉 in the case g=8. All the 3-transitive cubic graphs and exceptional 1- and 2-regular cubic graphs of girth at most 9 appear in the list of cubic symmetric graphs up to 768 vertices produced by Conder and Dobcsányi [M. Conder, P. Dobcsányi, Trivalent symmetric graphs up to 768 vertices, J. Combin. Math. Combin. Comput. 40 (2002) 41–63]; the largest is the 3-regular graph F570 of order 570 (and girth 9). The proofs of the main results are computer-assisted.
Journal: Journal of Combinatorial Theory, Series B - Volume 97, Issue 5, September 2007, Pages 757-768