Open Access System for Information Sharing

Login Library


Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

A contribution to the theory of distance-regular graphs

A contribution to the theory of distance-regular graphs
Date Issued
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 shows that 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 is based 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 about half 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].
Article Type
Files in This Item:
There are no files associated with this item.


  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Views & Downloads