混合循環(huán)圖的特征值

許英

（新疆財(cái)經(jīng)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，新疆 烏魯木齊 830012）

混合循環(huán)圖的特征值

許英

（新疆財(cái)經(jīng)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，新疆 烏魯木齊 830012）

一個(gè)圖的鄰接矩陣的特征值我們稱為這個(gè)圖的特征值，在物理和化學(xué)領(lǐng)域中，通過對物質(zhì)分子所對應(yīng)的分子圖的特征值的研究，可以預(yù)知該物質(zhì)在某些物理和化學(xué)方面的性質(zhì)。而在計(jì)算機(jī)網(wǎng)絡(luò)中，研究網(wǎng)絡(luò)對應(yīng)的圖的特征值將為深入研究該網(wǎng)絡(luò)提供一個(gè)非常有用的代數(shù)工具。因此，計(jì)算特殊圖類的特征值是圖譜理論中令大家感興趣的問題。在這篇文章中，我們研究了混合循環(huán)圖和混合循環(huán)有向圖的特征值的問題。

混合循環(huán)圖；鄰接矩陣；特征值

設(shè)G是一個(gè)單位元為1的有限群，S是G1的一個(gè)子集。群G關(guān)于集合S的Cayley有向圖D=D（G，S）是一個(gè)點(diǎn)集為G的有向圖，對于點(diǎn)g1，g2∈G，從g1到g2有一條弧當(dāng)且僅當(dāng)g2g1-1∈S。如果S是逆閉的，即S=S-1，則Cayley有向圖D（G，S）被認(rèn)為是一個(gè)無向圖，被稱為群G關(guān)于S的Cayley圖，表示為C（G，S）。在文獻(xiàn)[5]中，L.Lovasz確定了關(guān)于傳遞自同構(gòu)群的譜。在文獻(xiàn)[1]中，L.Babai得到了關(guān)于群G不可約特征的Cayley圖X（Γ，S）的譜的表達(dá)式。為了研究半對稱圖（正則邊傳遞但不是點(diǎn)傳遞的圖），文獻(xiàn)[6]中定義了雙Cayley圖。設(shè)G是一個(gè)有限群，S是G的一個(gè)子集，雙-Cayley圖BC（G，S）是一個(gè)點(diǎn)集為G×{0，1}的二部圖，邊集為{{（g，0），（sg，1）}：g∈G，s∈S}。當(dāng)G是一個(gè)循環(huán)群時(shí)，雙-Cayley圖BC（G，S）被稱為雙循環(huán)圖。雙-Cayley圖可以推廣到雙-Cayley有向圖上。對于一個(gè)有限群G和群G的子集T1，T2，群G的關(guān)于T1和T2的雙-Cayley有向圖D=（V（D）），E（D）=D（G，T1，T2）被定義為二部有向圖，點(diǎn)集為V（D）=G×{0，1}，并且對于點(diǎn)g1，g2∈G，（（g1，0），（g2，1））∈E（D）當(dāng)且僅當(dāng)g2=t1g1，其中t1∈T1；（（g1，1），（g2，0））∈E（D）當(dāng)且僅當(dāng)g1=t2g2，其中t2∈T2。如果，則D是k-正則圖。在文獻(xiàn)[8]中，作者得到了雙循環(huán)圖的譜。受到雙-Cayley圖定義的啟發(fā)，文獻(xiàn)[3]中作者定義了混合Cayley圖。設(shè)S1，S2，S是群G的子集，其中1G?Si且Si-1=Si，i=1，2，混合Cayley圖X=MC（G，S1，S2，S）的點(diǎn)集為V（X）=G×{0，1}邊集為E（X）=E0∪E1∪E2其中Ei={{（g，i），（sig，i）}：g∈G，si∈Si}，i=1，2；并且E0={{（g，0），（sg，1）}：g∈G，s∈S}。如果群G是循環(huán)群Zn，混合Cayley圖被稱為混合循環(huán)圖。類似的，我們可以推廣混合Cayley圖到混合Cayley有向圖上。設(shè)S1，S2，T1，T2是群G的子集。其中1G?Si，混合Cayley有向圖D=MD（G，S1，S2，T1，T2）的點(diǎn)集為V（D）=G×{0，1}，弧集為E（D）=E1∪E2∪E0，其中Ei={{（g，i），（sig，i）}：g∈G，si∈Si}，i=1，2且E0=E（D（G，T1，T2））。如果G=Zn，混合Cayley有向圖被稱為混合循環(huán)有向圖。在這篇文章中，我們將要研究混合循環(huán)圖和混合循環(huán)有向圖的特征值的問題，給出了混合循環(huán)圖和混合循環(huán)有向圖的特征值的顯的表達(dá)式。

引理1.1（Horn[4]）設(shè)A，B，C，D是n×n矩陣，并且0，AC=CA，則

一、混合循環(huán)圖的特征值

在這一節(jié)，我們將要考慮混合循環(huán)圖的特征值，我們給出了它的一個(gè)顯式表達(dá)式。設(shè)W表示首行為[0，1，0，…，0]的循環(huán)矩陣，設(shè)S表示一個(gè)一般的循環(huán)矩陣，首行為[s1，s2，…，sn]，則可以直接計(jì)算得到因?yàn)榫仃嘩的特征值為1，ω，ω2，…，ωn-1，其中ω=exp（2πi/n），由此可以得到循環(huán)矩陣S的特征值為λr=∑Sjω（j-1）r，r=0，1，…，n-1。

引理2.1設(shè)G=Zn1×…×Znt是一個(gè)循環(huán)群，并且S1，S2是群G的子集，矩陣和B，則我們有AB=BA且其中t=0， 1，2，…。

定理2.2 設(shè)X=MC（Zn，S1，S2，S）是一個(gè)混合循環(huán)圖，則圖X的特征值為n-1。其中

二、混合循環(huán)有向圖的特征值

下面我們將要考慮混合循環(huán)有向圖的特征值。

定理3.1設(shè)D=MD（Zn，S1，S2，T1，T2）是一個(gè)混合循環(huán)有向圖，則圖D的特征值為…，n-1，其中

本文主要討論了混合循環(huán)圖和混合循環(huán)有向圖的特征值的問題，利用代數(shù)工具給出了混合循環(huán)圖的特征值的顯的表達(dá)式，為進(jìn)一步研究混合Cayley圖的性質(zhì)帶來了便利。

[1]L.Babai，Spectra of Cayley graph[Z].J.Combin.Theory Ser.B 1979，（27）：180-189.

[2]N.Biggs，Algebraic Graph theory[Z].Amsterdam：North-Holland，1985.

[3]Jinyang Chen，Jixiang Meng，Lihong Huang [Z].Supper edge-connectivity of mixed Cayley graph[Z].Discrete Mathematics，2009，（309）：264-270.

[4]T.A.Horn，C.R.Johnson，Matrix analysis[Z].Cambridge：Cambridge University Press，1985.

[5]L.Lovasz，Spectra of graphs with transitive groups[Z].Period. Math.Hungar 6（1975）：191-196.

[6]M.Y.Xu，Introduction ofˉnite groups II[Z].Beijing：Science Press，1999（in Chinese）.

[7]F.J.Zhang，G.N.Lin，The complixity of digraphs[Z].In：Capobianco MF，Guan M.Hsu DF，eds.Graphs Theory and Its Aplication East and West，1989：171-180.

[8]H.Zou，J.X.Meng，Some algebraic properties ofBi-Cayley Graphs[Z].Acta Mathematica Sinica，Chinese Series 2007，50（5）：1075-1080.

G642.3

A

1674-9324（2014）14-0128-02

新疆財(cái)經(jīng)大學(xué)博士基金項(xiàng)目。

許英（1981-），女，新疆烏魯木齊，副教授，博士，從事圖論及其應(yīng)用、運(yùn)籌學(xué)等研究。