具有相同路徑層矩陣不同構(gòu)的r-正則圖.pdf

1、圖論是應(yīng)用數(shù)學(xué)理論的重要分支.圖論的廣泛應(yīng)用,促進(jìn)了它自身的發(fā)展.尤其是近幾十年來,隨著計算機(jī)技術(shù)的出現(xiàn)和進(jìn)步,圖論理論有了飛速的發(fā)展并取得了驚人的成績.該文所研究的具有相同路徑層矩陣不同構(gòu)的圖的問題是在藥品分析的實際應(yīng)用領(lǐng)域中提出來的.一個圖G的路徑層矩陣τ(G)(the path layer matrix)包含關(guān)于圖G中的所有路徑的定量信息.矩陣元素τi,j表示圖G中起點為i,路徑長度為j的路徑數(shù).圖的路徑層矩陣與圖的同構(gòu)問題密切相

2、關(guān).記f(r)為具有相同路徑層矩陣的不同構(gòu)的r-正則圖的最少頂點數(shù).求解任意r-正則圖的f(r)是一件非常有意義且很有難度的工作.1990年,Dobrynin構(gòu)造出了一系列具有相同路徑層矩陣不同構(gòu)的正則圖,證明了對于任意r≥3,存在具有相同路徑層矩陣的不同構(gòu)的r-正則圖(A.A.Dobrynin.Regular graphs having the same path layer matrix.J GraphTheory,1990,14:

3、141-148).在這篇論文中,Dobrynin給出的上界結(jié)果是f(r)≤18r+36 (r=2m,m≥3),f(r)≤20r+48(r=4m+3,m≥1),f(r)≤20r+64(r=4m+5,m≥0).2002年,楊元生等將結(jié)果改進(jìn)到f(5)≤48,f(6)≤51(楊元生,林建華,王春立.Small reguhlargraphs having the same path layer matrix.J Graph Theory,200

4、2,39:2l 9-221).在該文之前,沒有人能夠給出具有相同路徑層矩陣不同構(gòu)的任意r-正則圖的更好的統(tǒng)一構(gòu)造方法,r為任意值時的f(r)的上界也沒有得到改進(jìn).該文對路徑層矩陣相關(guān)問題進(jìn)行了深入研究,設(shè)計出了新的構(gòu)圖方案,利用3-相似圖的性質(zhì),結(jié)合類似于完全二部圖的連接方式,成功地構(gòu)造出了一系列具有相同路徑層矩陣但不同構(gòu)的r-正則圖,并給出了其正確性的完整數(shù)學(xué)證明.該文將f(r)的上界降至f(r)≤2r+20(r=3,5),f(r)≤