幾類重要Cayley圖的自同構(gòu)群研究.pdf

1、決定Cayley圖的自同構(gòu)群是代數(shù)圖論中一個(gè)非常重要也十分活躍的研究課題.一般來說,要解決這個(gè)問題是非常困難的.近幾十年來,雖然關(guān)于Cayley圖的自同構(gòu)群己有很多結(jié)果,但是到目前為止,這個(gè)問題仍沒有希望能夠得到完全解決.
　　本文主要決定了幾類重要Cayley圖,如:錯(cuò)位圖、偶錯(cuò)位圖的張量冪以及著名的烙餅圖的自同構(gòu)群,也刻畫了其中一些圖類的重要不變量,如:色數(shù)、團(tuán)數(shù)、獨(dú)立數(shù)及譜等.值得一提的是,本文反復(fù)運(yùn)用圖的最大獨(dú)立集的結(jié)構(gòu)來

2、決定它的自同構(gòu)群,這種方法在目前己有的自同構(gòu)群研究中還不多見.本文工作主要圍繞以下幾個(gè)方面.
　　首先,關(guān)于錯(cuò)位圖,我們證明它的自同構(gòu)群是(R(Sn)(×) Inn(Sn))(×) Z2,其中R(Sn)和Inn(Sn)分別是對稱群Sn的右正則表示和內(nèi)自同構(gòu)群,Z2是Sn上的取逆映射生成的二階循環(huán)群;通過證明上述結(jié)果,我們得到一個(gè)對稱群上滿足某一條件的任意Cayley圖的自同構(gòu)群的階的上界.利用錯(cuò)位圖的自同構(gòu)群的結(jié)果,我們完全刻畫了

3、錯(cuò)位圖的所有邊軌道。另外,我們研究了它的譜,通過推導(dǎo)出一個(gè)它的對應(yīng)于二部劃分的特征值公式,我們決定了它的第二大特征值;作為這個(gè)結(jié)果的應(yīng)用,我們給出了錯(cuò)位圖等周常數(shù)的上下界,同時(shí),也得到它的二部密度的上界及香農(nóng)容量的確切值。
　　其次,對于偶錯(cuò)位圖的張量冪,我們刻畫了它的一些性質(zhì),包括:連通性、直徑、獨(dú)立數(shù)、團(tuán)數(shù)、色數(shù)等,并證明它的所有最大獨(dú)立集都是點(diǎn)穩(wěn)定子的陪集,這推廣了Ku和Wong[59]的一個(gè)結(jié)果;通過應(yīng)用它的最大獨(dú)立集的特

4、殊結(jié)構(gòu),我們證明:偶錯(cuò)位圖的q次張量冪的自同構(gòu)群是(R(Aqn)(×)(Inn(Sn)(S) Sq))(×)Zq2,其中R(Aqn)是交錯(cuò)群直積Aqn的右正則表示,Inn(Sn)是對稱群Sn的內(nèi)自同構(gòu)群, Zq2表示二階循環(huán)群的直積, Inn(Sn)(S)Sq代表Inn(Sn)和Sq的圈積。
　　最后對于烙餅圖,通過運(yùn)用它的有效控制集的刻畫結(jié)果,并深入分析圖本身的結(jié)構(gòu),我們證明:烙餅圖的自同構(gòu)群同構(gòu)于對稱群的右正則表示,即烙餅圖是