A contribution to the theory of distance-regular graphs

Abstract

For any two vertices x, y of a distance-regular graph, say at distance h, there are ph ij(x, y) vertices at distance i from x and j from y. It is know that the number ph ij(x, y) only depend on i, j and h and not on the specific pair x, y. The ph ij := ph ij(x, y) are called the intersection numbers. This showsthat a distance-regular graph has a lot of combinatorial symmetry.Sometimes the intersection numbers can determine a distance-regular graph uniquely up to isomorphism, for example the Petersen graph, but this is not true in general. However the intersection numbers are very important because they give a lot of combinatorial structures, for examples they determine the number of vertices, the eigenvalues, the multiplicities and so on, that is, the intersection numbers are good objects to characterize distance-regular graphs.Through this thesis we investigate the behavior of intersection numbers for distance-regular graphs, and we give some classifications of distance-regular graphs under certain conditions on the intersection numbers.This thesis is mainly based on the paper [21] and the three preprints [22], [23] and [27], and is organized as follows.In Chapter 1, we first introduce distance-regular graphs, and then we give some examples and properties of distance-regular graphs.In Chapter 2, we give some results on the eigenvalues of distance-regular graphs and also give a lower bound on the second largest eigenvalue of a distance-regular graph in terms of intersection numbers. This is based on [21] and [22].In Chapter 3, we first look at distance-regular Terwilliger graphs, which have no induced quadrangle, and then we give some results on distance-regular Terwilliger graphs with intersection number c2 at least two. This isbased on [22] and [27].In Chapter 4, we study distance-regular graphs with diameter three which attain equality in the lower bound of the second largest eigenvalue of Chapter 2. We also give a new existence condition for distance-regular graphs. This is based on [21].In Chapter 5, we study distance-regular graphs which have a pair of distinct vertices such that the number of common neighbors of them is abouthalf the valency. Also, we give a classification of distance-regular graphs with b1/c2 ≤ 3/2 . This is based on [22].In Chapter 6, we study a distance-regular graph with a fixed ratio bt/ct and show that there are finitely many distance-regular graphs with valency k > 2, diameter D ≥ 6 and b2/c2< C for a given C. This is based on [27].In Chapter 7, we study the relationship between the intersection number c2 and its diameter for a distance-regular graph. Besides the Hadamard graphs and the 5-cube, we show that c2 ≤ k/3 for D ≥ 4. Moreover we will show that besides the generalized dodecagon of order (1, 2), the 6-cube, the Biggs-Smith graph, the 7-cube, the Foster graph, we show that c2 ≤ k/4 for D ≥ 6. This is based on [23].