Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Constructions for cubic graphs with large girth"

Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Constructions for cubic graphs with large girth. | Constructions for cubic graphs with large girth Norman Biggs Department of Mathematics London School of Economics Houghton St. London WC2A 2AE UK n.l.biggs @lse.ac.uk Submitted October 11 1997 Accepted August 31 1998 Abstract The aim of this paper is to give a coherent account of the problem of constructing cubic graphs with large girth. There is a well-defined integer o g the smallest number of vertices for which a cubic graph with girth at least g exists and furthermore the minimum value gu g is attained by a graph whose girth is exactly g. The values of J.-0 g when 3 g 8 have been known for over thirty years. For these values of g each minimal graph is unique and apart from the case g 7 a simple lower bound is attained. This paper is mainly concerned with what happens when g 9 where the situation is quite different. Here it is known that the simple lower bound is attained if and only if g 12. A number of techniques are described with emphasis on the construction of families of graphs Gi g for which the number of vertices Hi and the girth gi are such that Hi 2cgi for some finite constant c. The optimum value of c is known to lie between 0.5 and 0.75. At the end of the paper there is a selection of open questions several of them containing suggestions which might lead to improvements in the known results. There are also some historical notes on the current-best graphs for girth up to 36. MR Subject Numbers 05C25 05C35 05C38. 1. Introduction The aim of this paper is to give a coherent account of a topic which has been studied in a rather haphazard fashion for many years. There is much that remains to be done but recent advances particularly in geometric and computational group theory promise to throw some light on the darker corners of the subject. We shall concentrate on cubic graphs that is graphs in which each vertex has degree three. There are several justifications for this the first one being that cubic THE ELECTRONIC JOURNAL OF COMBINATORICS 5 1998 A1 2 .