A valency bound for distance-regular graphs
A valency bound for distance-regular graphs
复制标题
距离正则图的价界
DOI：
10.1016/j.jcta.2017.11.008
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Koolen Jack
中科院分区：
文献类型：
--
作者：
Qiao Zhi;Koolen Jack
正则完全t部图Kt×S(S，t个正整数至少2)的度k=(t−1)S有最小本征值−S=−k/(t−1)，因此，对于固定的t，有无穷多个正则完全t部图.在本文中，我们将证明这些图是距离正则图类的例外图。为此，我们将给出具有相对较大的绝对值最小特征值的距离正则图的价界。利用这个界，我们对直径不超过3且最小特征值不大于−k/2的非二部距离正则图进行了分类，其中k是图的度。作为应用，我们完成了直径为3的3-色距离正则图的分类，这是由Blokhuis，Brouwer和Haemers开始的。
The regular complete t-partite graphs K t× 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.