混合循環圖的特征值

許英

（新疆財經大學 應用數學學院，新疆 烏魯木齊 830012）

混合循環圖的特征值

許英

（新疆財經大學 應用數學學院，新疆 烏魯木齊 830012）

一個圖的鄰接矩陣的特征值我們稱為這個圖的特征值，在物理和化學領域中，通過對物質分子所對應的分子圖的特征值的研究，可以預知該物質在某些物理和化學方面的性質。而在計算機網絡中，研究網絡對應的圖的特征值將為深入研究該網絡提供一個非常有用的代數工具。因此，計算特殊圖類的特征值是圖譜理論中令大家感興趣的問題。在這篇文章中，我們研究了混合循環圖和混合循環有向圖的特征值的問題。

混合循環圖；鄰接矩陣；特征值

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

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

一、混合循環圖的特征值

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

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

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

二、混合循環有向圖的特征值

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

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

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

[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

新疆財經大學博士基金項目。

許英（1981-），女，新疆烏魯木齊，副教授，博士，從事圖論及其應用、運籌學等研究。