کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657541 1343746 2007 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Symmetric cubic graphs of small girth
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Symmetric cubic graphs of small girth
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 97, Issue 5, September 2007, Pages 757-768