Font Size: a A A

The Distance Regular Graphs With Order (2, 3) And Even Geometric Girth

Posted on:2009-05-30Degree:DoctorType:Dissertation
Country:ChinaCandidate:Y ZhangFull Text:PDF
GTID:1100360242995184Subject:Applied Mathematics
Abstract/Summary:PDF Full Text Request
Graph theory is a new branch of mathematics which is developing very rapidly in recentdecades. Since the ancient determination of the five platonic solids, the study of symmetry andregularity has always been one of the most fascinating aspects of mathematics, and even nowthere are many challenging problems in this area. Many regularity properties are naturallyexpressible in terms of an association scheme, which is by far the most important unifyingconcept in algebraic combinatorics. The P-polynomial association schemes (i.e., those with alinear distribution diagram with respect to some relation) are essentially the same objects asdistance regular graphs.Distance regular graphs were first defined by a British mathematician N.L.Biggs inthe 1970s. Since then, he and other mathematicians such as A.D.Gardiner, D.H.Smiths,A.E.Brouwer, E.Bannai and T.Ito established the main theory. In recent decades, the researchof the theory becomes so activity that it has established close ties with graph theory, designtheory, code theory, geometry and group theory. It is an important branch of Algebraic Com-binatorics.The classification of distance regular graphs is one of the most important problem at all.Ivanov proved that the diameter d(Γ) of a distance regular graphΓis bounded by a functionof the valency k and r(Γ). So in order to classify distance regular graphs of fixed valency k,the major part of work is to give an upper bound of r(Γ).For a distance regular graphΓ, when a1 = 1 or c2 = 1, it is easy to see that everymaximal clique has size s+1 = a1 +2, thenΓdoes not have an induced subgraph isomorphicto K2,1,1. Then a distance regular graphΓis of order (s,t) for some s and t.SupposeΓis a distance regular graph ordered (s,t). When t = 0, 1, 2, the problem hasbeen solved by Mohar, Ito, Biggs, Boshier, Shawe, Taylor, Bannai, Hiraki, Nomura, Suzukiand Yamazaki for almost thirty years. For the case t = 3, not much is known. The distanceregular graphs of order (1, 3) are those with valency 4 and a1 = 0. In late 1980's, Bannaiand Ito proved that the diameter of distance regular graphs of valency 4 is bounded, but thecomplete classification was not finished at that time. Until 1999, Brouwer and Koolen havesucceeded in completing the classification by use of computer. Suzuki pointed out that the condition s > 1 is very restrictive. In that sense, it is worth studying the following three cases:(s,t) = (2,3), (3,3), (4,3).Now the smallest unsolved case is the distance regular graphs or order (2, 3). So in thisthesis, we study the classification of the distance regular graphs with order (2, 3) and evengeometric girth.We use combinatorial methods and also algebraic methods in this thesis. Firstly, ana-lyzing the possible parameters in the intersection diagrams, obtain the finite cases by deletingthe impossible intersection numbers. Secondly, computing the upper bound of r through al-gebraic methods. Finally, noticing the well-known and very strong criterion for the existenceof a distance regular graph with given intersection array is the condition that the multiplicitiesof eigenvalues must be integral, we compute the finite cases and delete the non-integral oneswhich gives the most important preparations for the complete classification.The thesis is divided into three parts. The first part is devoted to the summarization ofthe dissertation. We discuss the development of the subject, including the background and thecurrent situations of it, the basic properties and methods used. In the second part, we analyzingthe possible parameters in the intersection diagrams, obtain the finite cases which only dependon r and s by deleting the impossible intersection numbers. In the thirty part, we compute themultiplicities of eigenvalues of the cases remained in the second part. Then we give the mostimportant preparations for the complete classification of the distance regular graphs ordered(2,3) and cr+1 > 1.
Keywords/Search Tags:distance regular graph, geometric girth, intersection array, eigenvalue of graph
PDF Full Text Request
Related items