階為（2，3）且?guī)缀螄L(zhǎng)為偶數(shù)的距離正則圖.pdf

1、圖論是近幾十年來發(fā)展十分迅速的一個(gè)新興的數(shù)學(xué)分支.從古老的5個(gè)柏拉圖立體開始，對(duì)稱和正則圖形始終是數(shù)學(xué)中最引人入勝的一個(gè)研究方向.即使是現(xiàn)在，這個(gè)領(lǐng)域仍有很多富有挑戰(zhàn)性的問題.許多正則性質(zhì)自然的表現(xiàn)為結(jié)合方案，其中P-多項(xiàng)式方案實(shí)質(zhì)上就是距離正則圖. 上世紀(jì)七十年代初，英國(guó)數(shù)學(xué)家Biggs首先提出距離正則圖這一概念，接著他和一批數(shù)學(xué)家Gardiner,Smiths，Brouwer,Bannai和Ito等建立了距離正則圖的基本理論

2、.近幾十年，距離正則圖理論的研究非常活躍，并且與圖論，設(shè)計(jì)理論，碼論，幾何論和群論都有密切的聯(lián)系，是代數(shù)組合論的一個(gè)重要分支. 距離正則圖的分類問題一直是距離正則圖研究中的一個(gè)重要的問題.Ivanov指出距離正則圖Г的直徑d(Г)由價(jià)k和r(Г)的函數(shù)定界，從而為了對(duì)固定價(jià)k的距離正則圖進(jìn)行分類，主要的工作就在于確定r(Г)的上界. 對(duì)于一個(gè)距離正則圖Г，當(dāng)α1=1或c2=1時(shí)，每一個(gè)極大團(tuán)的大小都為s+1=α1+2，不

3、存在同構(gòu)于K2,1，1的導(dǎo)出子圖，從而我們可以在此情形下只考慮階為(s，t)的距離正則圖. 對(duì)于階為(s，t)的距離正則圖.t=0，1，2時(shí)，Mohar,，Ito，Biggs，Boshier,Shawe-Taylor，Bannai，Hiraki，Nomura，Suzuki和Yamazaki等數(shù)學(xué)家經(jīng)過二三十年的研究，已經(jīng)完全解決了.t=3時(shí)并沒有太多相關(guān)分類的結(jié)論.當(dāng)s=1時(shí)，階為(1，3)的距離正則圖是價(jià)為4，α1=0的圖.上

4、世紀(jì)八十年代末，Bannai和Ito證明了價(jià)為4的距離正則圖的直徑存在界，但當(dāng)時(shí)并沒有得到完整的分類.直到1999年，Brouwer和Koolen應(yīng)用計(jì)算機(jī)搜索，得到了這類圖的完全分類.Suzuki指出：s＞1是一個(gè)限制性很強(qiáng)的條件，在t=3時(shí)，對(duì)階為(2，3)，(3，3)，(4，3)的距離正則圖的研究是很有意義的. 目前尚未解決的最小的情形就是階為(2，3)的距離正則圖，本文我們所考慮的就是階為(2，3)并且?guī)缀螄L(zhǎng)為偶數(shù)，即

5、cr+1＞1的距離正則圖的分類情況. 本文主要應(yīng)用組合和代數(shù)兩種方法.首先用組合方法分析交叉表中所有可能的參數(shù)，將不存在的交叉數(shù)排除，剩下有限多個(gè)僅依賴于r的交叉表的情形；第二步就是用代數(shù)方法進(jìn)行相關(guān)計(jì)算，得到r的上界；再應(yīng)用計(jì)算機(jī)對(duì)剩下的有限種情況一一計(jì)算，利用圖特征值重?cái)?shù)的整數(shù)性排除不可能的交叉表，從而大大壓縮了直徑d可能的范圍，為階為(2，3)，幾何圍長(zhǎng)是偶數(shù)的距離正則圖的完全分類起了重大的作用。 文章共分為三章.

6、 第一章主要介紹了有關(guān)距離正則圖的基本概念，性質(zhì)，以及研究背景和發(fā)展現(xiàn)狀. 第二章利用組合方法分析了所有滿足基本必要條件的交叉數(shù)，排除了不可能存在的交叉表參數(shù)，剩下的情形直徑d只與r和s的大小有關(guān). 第三章主要應(yīng)用代數(shù)方法和特征值理論，針對(duì)第二章剩下的各情形計(jì)算，得到r和s的上界，從而確定直徑d的范圍.進(jìn)一步利用計(jì)算機(jī)計(jì)算圖特征值的重?cái)?shù)，排除重?cái)?shù)非整數(shù)的情形，為階為(2，3)，cr+1＞1的距離正則圖的完全分類作