Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903803 | Journal of Combinatorial Theory, Series A | 2018 | 17 Pages |
Abstract
The regular complete t-partite graphs KtÃs (s,t positive integers at least 2) with valency k=(tâ1)s have smallest eigenvalue âs=âk/(tâ1), and hence, for fixed t there are infinitely many of them. In this paper we will show that these graphs are exceptional graphs for the class of distance-regular graphs. For this we will show a valency bound for distance-regular graphs with a relatively large, in absolute value, smallest eigenvalue. Using this bound, we classify the non-bipartite distance-regular graphs with diameter at most three with smallest eigenvalue not larger than âk/2, where k is the valency of the graph. As an application we complete the classification of the 3-chromatic distance-regular graphs with diameter three, which was started by Blokhuis, Brouwer and Haemers.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zhi Qiao, Jack Koolen,