论文部分内容阅读
本文介绍了距离正则图有关问题的进展. 在一个直径为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-路正则图是距离正则图的推广,它是由Dalfó等人引入的.当t=0时,t-路正则图也就是Godsil和McKay引入的路正则图.而当t为直径D时,t-路正则图为距离正则图. 在第一章中,我们介绍了一些基本的概念和研究工具,并介绍了相关问题的研究背景. 在第二章中,对任意固定的实数0<α<1和固定的直径D≥2,我们证明了只有有限多个共连通非二部的直径为D距离正则图,使得它的最小特征值θD不超过-αk,其中k为图的度.当D≤3或(D=4且a1≠0)时,我们完全分类了度为k,直径为D,最小特征值为θmin≤-k/2的距离正则图.Blokhuis等人确定了已知距离正则图中的3-染色距离正则图.将它同上面的结果结合起来,我们确定了直径D=3或(D=4且a1≠0)的3-染色距离正则图. Juri(s)i(c)等人引入了距离正则图的轻尾的概念,并且利用特征值θi和它的重数mi,给出了距离正则图的极小幂等元Ei为轻尾时的充要条件.在第三章中,我们利用轻尾给出了对偶极图2A2D-1(r)的刻画,并由此证明了直径为D,最小特征值为θmin=-k/2,且交叉数a1=1,c2≥4的距离正则图为2A2D-1(2). Koolen和Park分类了顶点数目相对图的度较小的距离正则图.在第四章中,我们介绍了包含对偶性质的分组设计和它们的关联图,并由此引入了一类2-路正则图.随后,我们推广了Koolen和Park的结果,对任意实数α>2,我们证明了度为k,直径D≥3,且顶点数目v≤αk的非距离正则的2-路正则图,除去有限多个之外,都来自包含对偶性质的分组设计的关联图. 在最后一章中,我们介绍了后续的研究问题.