距离正则图的若干问题研究

发布时间：2018-05-06 05:16

  本文选题：距离正则图 + 3-染色　； 参考：《中国科学技术大学》2016年博士论文

【摘要】：本文介绍了距离正则图有关问题的进展.在一个直径为D的图中,若存在常数ci，bi(0≤i≤D),使碍对图中任意距离为i的顶点X,y,在顶点y的邻点中,至到顶点X距离为i-1的顶点数目为Ci,到顶点X距离为i-1顶点数目为bi则这个图被称为距离三则图.距离正刚图是-类有着很强组合性质的图,它是由Biggs作为距离可迁图的推广而引入的.在一个图中,若对任意距离为i(0≤i≤t)的顶点x,y,它们之间任意固定长度的路的数目只与这对顶点之间的距离i相关,正与具体顶点的选取无关,则该图被称为t-路正则图.t-路正则图是距离正则图的推广,它是由Dalfo等人引入的.当t=0时,t-路正则图也就是Godsil和McKay引入的路正则图.而当t为直径D时,t-路正则图为距离正则图.在第一章中,我们介绍了一些基本的概念和研究工具,并介绍了相关问题的研究背景.在第二章中,对任意固定的实数0α1和固定的直径D ≥2,我们证明了只有有限多个共连通非二部的直径为D距离正则图,使得它的最小特征值θD不超过-αK,其中K为图的度.当D≤3或(D=4 (?) α1≠0)时,我们完全分类了度为k,直径为D,最小特征值为θmin≤-K/2的距离正则图Blokhuis等人确定了已知距离正则图中的3-染色距离正则图.将它同上面的结果结合起来,我们礁定了直径D=3或(D=4且α1≠0)的3-染色距离正贝则图.Jurisic芒等人引入了距离正则图的轻尾的概念,并且利用特征值θi和它的重数mi,给出了距离正则图的极小幂等元Ei为轻尾时的充要条件.在第三章中,我们利用轻尾给出了对偶极图2A2D-1(r)的刻画,并由此证明了直径为D,最小特征值为θmin=-k/2旦交叉数α1=1,c2≥4的距离正则图为2A2D-1(2).Koolen和Park分类了顶点数目相对图的度较小的距离正则图.在第四章中,我们介绍了包含对偶性质的分组设计和它们的关联图,并由此引入了一类2-路正则巨.随后,我们推广了Koolen和Park的结果,对任意实数α2,我们证明了度为K,直径D≥3,且顶点数目u≤αK的非距离正则的2-路正则图,除去有限多个之外,都来自包含对偶性质的分组设计的关联图.在最后一章中，，我们介绍了后续的研究问题.
[Abstract]:In this paper, we introduce the progress of the problems related to distance regular graphs. In a graph of diameters D, if there exists the constant cibbin 0 鈮

本文编号：1850941