圖的多項式唯一性.pdf

1、多年來，圖多項式一直是一個活躍的研究課題，它在圖論與傳統(tǒng)代數(shù)之間架起了橋梁。因為圖多項式的系數(shù)包含了豐富的組合信息，所以圖多項式的研究為我們了解圖的復(fù)雜結(jié)構(gòu)與參數(shù)提供了新的途徑。一個很自然的問題就是什么類型的圖能被它們的多項式唯一確定?特別地，什么類型的圖，它的結(jié)構(gòu)可以被一個圖多項式完全刻畫?換句話來說，我們是否可以找到一類圖使得他們可以被一個給定的多項式所確定?本文主要研究這些問題。
　　 圖論中有三個重要的多項式：色多項式、

2、Tutte多項式以及流多項式。這三個多項式有很密切的關(guān)系，其中色多項式與流多項式在某種意義上具有“對偶性”，并且它們都是Tutte多項式的特殊形式。色多項式以及能夠由色多項式唯一確定的圖等問題已得到深入研究，近些年，更多研究關(guān)注于Tutte多項式以及能夠由Tutte多項式唯一決定的圖。然而，關(guān)于流多項式，這方面的成果還屈指可數(shù)。另外，關(guān)于能被色多項式與流多項式所共同確定的圖方面的研究還是空白。本論文首次對這些問題進行了研究。
　　

3、 論文結(jié)果包括兩個方面的內(nèi)容。第一部分主要是對流多項式的研究以及能被色多項式與流多項式共同確定的圖的研究；第二部分主要涉及能被Tutte多項式所唯一確定的圖的研究。
　　 論文的第一部分包括第二章和第三章。在第二章中，我們主要關(guān)注圖的流多項式。我們研究了流多項式的系數(shù)，并且證明：若兩個連通的對偶簡單圖有相同的流多項式，那么他們有相同的點數(shù)、邊數(shù)、邊連通度以及相同數(shù)目的最小邊割。利用這些信息，我們得出了廣義θ－圖的對偶圖、5個頂

4、點的完全圖K5以及六個頂點的完全二部圖K3，3是可以被它們的流多項式所唯一確定的。
　　 在第三章中，我們綜合運用包含在色多項式與流多項式中的信息，證明了梯子、Mobius梯子以及圈平方圖可以被它的色多項式和流多項式所共同決定。而這幾類圖，de Mier和Noy曾證明它們是能被Tutte多項式所唯一確定的，這個結(jié)果可以看作是我們結(jié)論的推論。
　　 第二部分即第四章。在這一章中，我們研究了兩類圖：第一類圖我們稱作是“曲輪”