混合循环图的特征值

2014-09-01许英

教育教学论坛 2014年14期

摘要：一个图的邻接矩阵的特征值我们称为这个图的特征值，在物理和化学领域中，通过对物质分子所对应的分子图的特征值的研究，可以预知该物质在某些物理和化学方面的性质。而在计算机网络中，研究网络对应的图的特征值将为深入研究该网络提供一个非常有用的代数工具。因此，计算特殊图类的特征值是图谱理论中令大家感兴趣的问题。在这篇文章中，我们研究了混合循环图和混合循环有向图的特征值的问题。

关键词：混合循环图；邻接矩阵；特征值

中图分类号：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是一个循环群时，双-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。如果T1=T2=k，则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矩阵，并且A≠0，AC=CA，则A BC D=AC-CB。

一、混合循环图的特征值

在这一节，我们将要考虑混合循环图的特征值，我们给出了它的一个显式表达式。设W表示首行为[0，1，0，…，0]的循环矩阵，设S表示一个一般的循环矩阵，首行为[s1，s2，…，sn]，则可以直接计算得到S=■SjWj-1。因为矩阵W的特征值为1，ω，ω2，…，ωn-1，其中ω=exp（2πi/n），由此可以得到循环矩阵S的特征值为λr=∑Sjω（j-1）r，r=0，1，…，n-1。

引理2.1设G=Z■×…×Z■是一个循环群，并且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]的循环矩阵，我们很容易可以看到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）是一个混合循环图，则图X的特征值为■，r=0，1，…，n-1。其中q=（∑s■∈S■ω■+∑s■∈S■ω■）■-4（∑s■∈S■s■∈S■ω■-∑s■∈S■，s■∈Sω■）

∈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

ω■）。证毕。

二、混合循环有向图的特征值

下面我们将要考虑混合循环有向图的特征值。

定理3.1设D=MD（Zn，S1，S2，T1，T2）是一个混合循环有向图，则图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，通过一个简单的计算，我们可以得到混合循环有向图的特征值为■，r=0，1，…，n-1，其中p=

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

ω■）证毕。

本文主要讨论了混合循环图和混合循环有向图的特征值的问题，利用代数工具给出了混合循环图的特征值的显的表达式，为进一步研究混合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.

基金项目：新疆财经大学博士基金项目。

作者简介：许英（1981-），女，新疆乌鲁木齐，副教授，博士，从事图论及其应用、运筹学等研究。endprint