本文選題：距離正則圖 + 3-染色�。� 參考：《中國科學技術大學》2016年博士論文

【摘要】：本文介紹了距離正則圖有關問題的進展.在一個直徑為D的圖中,若存在常數(shù)ci，bi(0≤i≤D),使礙對圖中任意距離為i的頂點X,y,在頂點y的鄰點中,至到頂點X距離為i-1的頂點數(shù)目為Ci,到頂點X距離為i-1頂點數(shù)目為bi則這個圖被稱為距離三則圖.距離正剛圖是-類有著很強組合性質(zhì)的圖,它是由Biggs作為距離可遷圖的推廣而引入的.在一個圖中,若對任意距離為i(0≤i≤t)的頂點x,y,它們之間任意固定長度的路的數(shù)目只與這對頂點之間的距離i相關,正與具體頂點的選取無關,則該圖被稱為t-路正則圖.t-路正則圖是距離正則圖的推廣,它是由Dalfo等人引入的.當t=0時,t-路正則圖也就是Godsil和McKay引入的路正則圖.而當t為直徑D時,t-路正則圖為距離正則圖.在第一章中,我們介紹了一些基本的概念和研究工具,并介紹了相關問題的研究背景.在第二章中,對任意固定的實數(shù)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和它的重數(shù)mi,給出了距離正則圖的極小冪等元Ei為輕尾時的充要條件.在第三章中,我們利用輕尾給出了對偶極圖2A2D-1(r)的刻畫,并由此證明了直徑為D,最小特征值為θmin=-k/2旦交叉數(shù)α1=1,c2≥4的距離正則圖為2A2D-1(2).Koolen和Park分類了頂點數(shù)目相對圖的度較小的距離正則圖.在第四章中,我們介紹了包含對偶性質(zhì)的分組設計和它們的關聯(lián)圖,并由此引入了一類2-路正則巨.隨后,我們推廣了Koolen和Park的結果,對任意實數(shù)α2,我們證明了度為K,直徑D≥3,且頂點數(shù)目u≤αK的非距離正則的2-路正則圖,除去有限多個之外,都來自包含對偶性質(zhì)的分組設計的關聯(lián)圖.在最后一章中，，我們介紹了后續(xù)的研究問題.
[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