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

2014-09-01 02:23:02許英

教育教學論壇 2014年14期

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

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

中圖分類號：G642.3 文獻標志碼：A 文章編號：1674-9324（2014）14-0128-02

設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是一個循環(huán)群時，雙-Cayley圖BC（G，S）被稱為雙循環(huán)圖。雙-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。如果T1=T2=k，則D是k-正則圖。在文獻[8]中，作者得到了雙循環(huán)圖的譜。受到雙-Cayley圖定義的啟發(fā)，文獻[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是循環(huán)群Zn，混合Cayley圖被稱為混合循環(huán)圖。類似的，我們可以推廣混合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有向圖被稱為混合循環(huán)有向圖。在這篇文章中，我們將要研究混合循環(huán)圖和混合循環(huán)有向圖的特征值的問題，給出了混合循環(huán)圖和混合循環(huán)有向圖的特征值的顯的表達式。

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

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

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

引理2.1設G=Z■×…×Z■是一個循環(huán)群，并且S1，S2是群G的子集，矩陣A=∑（i1，…，it）∈S1W■■?茚…?茚W■■和B

=∑（j1，…，jt）∈S2W■■?茚…?茚W■■，則我們有AB=BA且AT=∑（i1，…，it）∈S1

W■■?茚…?茚W■■，BT=∑（j1，…，jt）∈S2 W■■?茚…?茚W■■，其中t=0，1，2，…。

證明：因為A=∑（i1，…，it）∈S1W■■?茚…?茚W■■，B=

∑（j1，…，jt）∈S2W■■?茚…?茚W■■，則我們有AB=∑■W■■?茚…?茚

W■■，且BA=∑■W■■?茚…?茚W■■。因此，AB=BA。因為W是首行為[0，1，…，0]的循環(huán)矩陣，我們很容易可以看到W是一個酉矩陣，則Wk也是酉矩陣，其中k＞0，則（Wk）T=Wn-k。因此，我們有AT=∑（i■，…，i■∈S■W■■…?茚W■■，BT=

∑（j■，…，j■）∈S■W■■?茚…W■■。其中t=0，1，2，…。證畢。

定理2.2 設X=MC（Zn，S1，S2，S）是一個混合循環(huán)圖，則圖X的特征值為■，r=0，1，…，n-1。其中q=（∑s■∈S■ω■+∑s■∈S■ω■）■-4（∑s■∈S■s■∈S■ω■-∑s■∈S■，s■∈Sω■）

證明：設A是混合循環(huán)圖X的鄰接矩陣，B，A1，A2分別是循環(huán)圖C（Zn，S），C（Zn，S1）和C（Zn，S2）的鄰接矩陣。由混合循環(huán)圖的定義，很容易可以看到A=A1 BBT A2。因此，我們有|λIzn-A|λIn-A1 -B -BT λIn-A1.（1）又因為（λIn-A1）（-BT）=-λBT+A1BT，（-BT）（λIn-A1）=-λBT+BTA1，由引理2.1.BT和A1是循環(huán)圖的矩陣，則BTA1=A1BT。又根據(jù)引理1.1，我們可以得到|λI2n-A|=|（λIn-A1）（λIn-A2）-BTB|=λ2In-λ（A2+A1）+A1A2-BTB=|λ2In-λ（∑s■∈S■W■+∑s■endprint

∈S■W■）+∑s■∈S■W■∑s■∈S■W■-（∑s■∈S■W■）■（∑s■∈S■W■）|=

|λ2In-λ（∑s■∈S■W■+∑s■∈S■W■）+（∑s■∈S■，s■∈S■W■-∑s■∈S■，s■∈S■

W■|=■（λ2-λ（∑s■∈S■ω■+∑s■∈S■ω■）+（∑s■∈S■，s■∈S■

ω■-∑s■∈S，s∈Sω■）），則矩陣A的特征值是下面多項式的根λ2-λ（∑s■∈S■ω■+∑s■∈S■ω■）+（∑s■∈S■，s■∈S■ω■-

∑s■∈S■，s■∈Sω■），r=0，1，…，n-1。

通過一個簡單的計算，我們有矩陣A的特征值為■，r=0，1，…，n-1，其中q=

（∑s■∈S■ω■+∑s■∈S■ω■）■-4（∑s■∈S■s■∈S■ω■-∑s■∈S■，s■∈S

ω■）。證畢。

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

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

定理3.1設D=MD（Zn，S1，S2，T1，T2）是一個混合循環(huán)有向圖，則圖D的特征值為■，r=0，1，…，n-1，其中p=（∑s■∈S■ω■+∑s■∈S■ω■）■-4（∑s■∈S1，s■∈S■

ω■-∑■，■ω■）。

=|λ2In-λ（∑s■∈S■W■+∑s■∈S■W■）+∑s■∈S■W■∑s■∈S■W■-（∑■W■）（∑■W■）|=|λ2In-λ（∑s■∈S■W■+∑s■∈S■W■）+

（∑s■∈S■，s■∈S■W■-∑■，■W■）|=■（λ2-λ（∑s■∈S■ω■+∑s■∈S■ω■）+（∑s■∈S■，s■∈S■ω■-∑■，■ω■）），則A的特征值是下面多項式的根，λ2-λ（∑s■∈S■ω■+∑s■∈S■ω■）+（∑s■∈S■，s■∈S■ω■-∑■，■ω■），r=0，1，…，n-1，通過一個簡單的計算，我們可以得到混合循環(huán)有向圖的特征值為■，r=0，1，…，n-1，其中p=

（∑s■∈S■ω■+∑s■∈S■ω■）■-4（∑s■∈S■s■∈S■ω■-∑■，■

ω■）證畢。

本文主要討論了混合循環(huán)圖和混合循環(huán)有向圖的特征值的問題，利用代數(shù)工具給出了混合循環(huán)圖的特征值的顯的表達式，為進一步研究混合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 of Bi-Cayley Graphs[Z].Acta Mathematica Sinica，Chinese Series 2007，50 （5）：1075-1080.

基金項目：新疆財經(jīng)大學博士基金項目。

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