混合Cayley圖的譜*

陳淑蘋 陳金陽(yáng) 謝 濤

(湖北師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，湖北黃石435002)

0 引言

近30年，人們開始研究圖的代數(shù)性質(zhì)，隨著計(jì)算機(jī)科學(xué)的迅猛發(fā)展，這個(gè)領(lǐng)域中的大量研究已經(jīng)逐漸由國(guó)外向國(guó)內(nèi)滲透.圖論的代數(shù)性質(zhì)也能被運(yùn)用于許多領(lǐng)域，如通信理論、微軟工程等.

為了把圖和代數(shù)結(jié)合起來(lái)，學(xué)者們需要先引進(jìn)一個(gè)概念，即圖的鄰接矩陣:v × v 矩陣A(G)=［aij］，其中aij是連接vi和vj的邊的數(shù)目.這樣每個(gè)圖都能有相應(yīng)的鄰接矩陣和它對(duì)應(yīng)，那么我們?cè)谘芯繄D的代數(shù)性質(zhì)時(shí)，實(shí)際上就是研究這個(gè)圖相對(duì)應(yīng)的鄰接矩陣.鄰接矩陣的一個(gè)重要的不變量就是它的特征值，所以研究圖的特征值是非常重要的.圖的M－特征值是圖矩陣M 的特征值.圖的M－譜是由M－特征值序列組成記做Spec M(G).如果Spec M(G)= Spec M(H)，則稱G 和H 是M－同譜圖，并表示為G－M H.記G 的M－同譜類為［G］M ={H|H－MG}.若對(duì)于任意滿足G－M H 的圖H 都有，則稱G 是由M－譜所確定的.

Cayley 圖是A.Cayley 在1878年提出的，當(dāng)時(shí)是為了解釋生成元和群定義的關(guān)系而提出的，但是由于它構(gòu)造的簡(jiǎn)單性，品種的多樣性和高度的對(duì)稱性，越來(lái)越多的受到了圖論學(xué)者的重視，成為群和圖開辟出來(lái)的一個(gè)新領(lǐng)域.近幾十年來(lái)，隨著計(jì)算機(jī)的迅猛發(fā)展，人們發(fā)現(xiàn)Cayley 圖是構(gòu)造和設(shè)計(jì)互聯(lián)網(wǎng)絡(luò)的一種很好的數(shù)學(xué)模型，所以又獲得了實(shí)際的應(yīng)用，它的重要性就顯得更加突出.

定義1［1］設(shè)G 是單位元為1G的群，S 是G 的任一不含單位元的非空子集，且滿足S－1=S，則Cayley 圖C(G，S)的頂點(diǎn)集合V = G，邊集E ={(x，y)|x－1y∈S}.

Cayley 圖是一類典型的點(diǎn)傳遞圖.根據(jù)Cayley 圖的定義，徐明曜給出了一類二部Cayley 圖的概念:

定義2［1］設(shè)G 是單位元為1G的群，S 是G 的任一非空子集，則二部Cayley 圖BC(G，S)的頂點(diǎn)集為V = G × {0，1}，邊集E ={{(g，0)，(sg，1)}|g∈G，s∈S}.

而作為Cayley 圖和二部Cayley 圖的推廣，陳金陽(yáng)給出了混合Cayley 圖的概念:

定義3［2］設(shè)G 是單位元為1G的群，S0，S1，S2是G 的子集，且滿足Si=S－1i，1G?Si，i=(0，1)，則混合Cayley 圖MC(G，S0，S1，S2)的頂點(diǎn)集為V =G ×{0，1}，邊集E =E0∪E1∪E2，其中當(dāng)S2=? 時(shí)，MC(G，S0，S1，S2)?C(G，S0)∪C(G，S1);當(dāng)S0= S1= ? 時(shí)，MC(G，S0，S1，S2)?BC).

因此，Cayley 圖和二部Cayley 圖是混合Cayley 圖的特殊情況.混合Cayley 圖是陳金陽(yáng)提出的一個(gè)全新的概念，它是一類半正則半傳遞圖，因此是一類更具有一般性、拓?fù)浣Y(jié)構(gòu)更好的圖類。除了陳金陽(yáng)對(duì)其邊連通性和超邊連通性做了一些研究外，目前國(guó)內(nèi)外同行還沒有對(duì)此類圖做過(guò)研究，因此具有較高的研究?jī)r(jià)值.

在本文中，我們根據(jù)混合Cayley 圖和Cayley 圖與二部Cayley 圖之間的聯(lián)系，研究了Cayley 圖和二部Cayley 圖的鄰接矩陣在正規(guī)的情況下，混合Cayley 圖的相鄰矩陣，并計(jì)算出了混合Cayley 圖的譜.

1 混合Cayley 圖的譜

一個(gè)矩陣A∈Cn×n是正規(guī)的，如果A*A =AA*，這里的A*表示A 的復(fù)共軛轉(zhuǎn)置矩陣.

引理1［3］Cayley 圖的鄰接矩陣是正規(guī)的.

引理2［3］二部Cayley 圖的鄰接矩陣是正規(guī)的.

引理3［3］假設(shè)A，B，C，D 是n × n 矩陣，|A|≠0，AC =CA，則.

引理4［3］設(shè)A 是一個(gè)正規(guī)矩陣，λ1，λ2，…，λn是它的特征值，則存在一個(gè)酉矩陣U 使得.

引理5［3］設(shè)λ1，λ2，…，λn是Cayley 圖C(G，S)的特征值，則二部Cayley 圖BC(G，S)的特征值是±λ1，±λ2，…，±λn.

引理6［4］設(shè)A，B 是可對(duì)角化的，若它們是可交換的，則A，B 是相似對(duì)角化的.

2 主要結(jié)果

定理1設(shè)λ1，λ2，…，λn是Cayley 圖C(G，S0)的特征值，設(shè)κ1，κ2，…，κn是二部Cayley 圖BC(G，S1)的特征值，如果C(G，S0)和C(G，S1)的鄰接矩陣是正規(guī)的和可交換的，則混合Cayley 圖MC(G，S0，S1，S2)的相鄰矩陣的特征值是κ1±λ1，κ2±λ2，…，κn±λn.

證明設(shè)A，B，C 分別是BC(G，S1)，C(G，S0)和MC(G，S0，S1，S2)的鄰接矩陣，則有，由引理3 得到:

因?yàn)锳 和B 都是正規(guī)的，由引理4 可知，存在一個(gè)酉矩陣滿足:

又因?yàn)锳 和B 都是可交換的，由引理6 可得到:

因此混合Cayley 圖的MC(G，S0，S1，S2)的譜是κ1±λ1，κ2±λ2，…，κn±λn.

3 結(jié)束語(yǔ)

本文研究了混合Cayley 圖的代數(shù)性質(zhì)，把混合Cayley 圖與代數(shù)問題結(jié)合起來(lái)，能有效的解決混合Cayley 圖的許多問題.本文主要得到了混合Cayley 圖連通時(shí)的譜，用更具體的數(shù)字化形式來(lái)衡量圖的一些問題，為我們更加直觀的研究圖的性質(zhì)帶來(lái)了方便.

［1］徐明曜.有限群導(dǎo)引［M］.北京:科學(xué)出版社，2001:349－367

［2］Chen Jinyang，Meng Jixiang，Huang Lihong.Super edge－connectivity of mixed Cayley graph［J］.Discrete Mathematics，2009，309:264－270

［3］鄒華.Bi－Cayley 圖的一些代數(shù)性質(zhì)［J］.新疆大學(xué)學(xué)報(bào)，2007(5):117－122

［4］R A Horn，C R Johnson.矩陳分析［M］.楊奇，譯.北京:機(jī)械工業(yè)出版社，2005:156－174