反循环图的一些代数性质及其推广

许英+王冉冉

摘 要 一个图被称为反循环图，如果这个图的邻接矩阵是一个反循环矩阵。在本文中，我们将定义双反循环图，并且给出它的谱，图的谱是图的一种重要性征，在物理和化学领域中，通过对物质分子所对应的分子图的谱的研究，可以预知该物质在某些物理和化学方面的性质，例如，图的谱与图所对应化学分子的能量有关。另外，我们将研究双反循环图的支撑树个数的渐进计数定理，图的支撑树数是图的重要的不变量，也是网络可靠性的重要的量度。

关键词 Cayley和图 反循环图 支撑树 谱

中图分类号：O151 文献标识码：A DOI：10.16400/j.cnki.kjdkz.2015.06.014

Some Algebraic Properties and Promotion of Reverse Circulation Figure

XU Ying[1]， WANG Ranran[2]

（[1] College of Applied Mathematics， Xinjiang University of Finance & Economics， Urumqi， Xinjiang 830012;

[2] Xinjiang Urumqi Autonomous Region Disease Control Center， Urumqi， Xinjiang 830002）

Abstract A graph is called a reverse circulation diagram， if the adjacency matrix is a matrix of reverse circulation. In this article， we will define dual circulation map and giving its spectrum， spectral graph is an important feature of diagram， in the field of physics and chemistry， the study of the material elements of the corresponding molecular graph of the spectrum， you can predict the properties of the substance in certain physical and chemical aspects of， for example， the spectrum and the diagram corresponds to the energy of chemical molecules related. in addition， we will study the progressive count the number of Spanning Tree Theorem double reverse circulation figure， the number of spanning tree diagram is important graph invariants， is also an important measure of network reliability.

Key words Cayley and figure; reverse circulation figure; spanning tree; spectrum

1 引言

设是一个有个点的简单图，点集为 = （） = {，，…，}边集为 = （）。图的邻接矩阵被定义为一个阶矩阵 = （） = []，其中 = 1如果和是相邻的，否则 = 0。因为是实对称矩阵，所以可以设的特征值为：（）≤（）≤…≤（）。

设是一个有限群，是群的子集。的关于的有向图 = （，）是一个点集为的有向图，对，，到有一条弧当且仅当。当是循环群时，有向图（，）被称为一个循环有向图。

设是一个有限群，是群的子集，我们用（）表示的关于的和图，和图（）是一个无向图，点集为，边集为{（，） €？： + }。如果存在使得，则边（，）是一个半边：半边是只有一个端点的边。

关于和图的研究成果已经有很多，例如，和图的哈密尔顿圈; 和图的独立数。和图的直径与特征值之间的关系;和图的团数;和图的连通度。在文献[4]中，M.Amooshahi等人定义了反循环图并且研究了反循环图的一些性质，另外，他们还证明了一个图是反循环图当且仅当它是一个循环群上的和图。

反移位作用 ：→定义为（，，…，） = （，，…，，）。反循环矩阵是一个关于向量 = （，，…，）的 €？矩阵，它的行是由反移位作用来确定，也就是，第行是， = 1，2，…，。

一个有个点的图被称为反循环图，如果它有反循环邻接矩阵，即 = []（）是反循环矩阵，当且仅当 = 对所有的。

类似于双循环图，我们定义双反循环图。设是循环群，是的子集，双反循环图（，）是一个二部图，点集为  €？{0，1}边集为{{（，0），（，1）}：，}，很容易可以看到双反循环图（，）是一个点数为2的正则图。在本文中，我们将讨论双反循环图的谱和它的支撑树个数的渐进定理。

下面，我们引入几个在下一节需要用到的已知结果。

引理1.1 （Horn [1]）.设，，，是 €？矩阵，且∣∣≠ 0，  = ，则。

设表示首行为[0，1，0，…，0]的循环矩阵。

引理1.2 （Biggs [2]）.设 = （，）是一个循环图。则的邻接矩阵是 = ，的特征值为 = ， = 0，1，…， ，其中 = （/），注意{ ： 0≤≤}是方程 = 1的所有的解，它们被称为次单位根。

引理1.3 （Biggs [2]）.设是一个连通正则图，它的谱为

则的支撑树的个数为（） = 。

2 双反循环图的谱

在这一节，我们将要谈论双反循环图的特征值。

引理2.1.设，是 €？的反循环矩阵，首行元素是0或者1，则是一个循环矩阵。

证明：设反循环矩阵 = （）， = （），矩阵，的乘积 =  = （）

根据矩阵乘积的定义，我们有

=   =  +  + … +

=   =  +  + … +

（1）

其中角标都模。

由于和都是反循环矩阵，即，

= ， = ， = ，…， =

= ， = ， = ，…， =

（2）

由（1）（2）两式，我们很容易可以看出 = ，这意味着矩阵是一个循环矩阵。

设双反循环图（，）的邻接矩阵为，是反循环图（）的邻接矩阵。由双反循环图的定义，很容易可以看出。

因此，我们可以得到矩阵的特征多项式

（3）

因为是首行为（，，，…，）的反循环矩阵，且

由引理2.1， = 是循环矩阵，首行为（，，…，）。为了表示出的首行元素，我们设反循环集 = ，构造集合 = （模），（ = 1，2，…，），即中的每一个元素都减1，我们就得到了集合。设 = ∣∣= ，  =∣∩∣，…， =∣∩∣，则我们可以得到 = ，  = ，  = ，…， = ，由于是一个循环矩阵，则 = ，因此可以得到的特征值为 = ， = 0，1，2，…，。

由（3）式可得矩阵的特征值为 = €？ = €保ǎ？= 0，1，2，…，。

又根据双反循环图（，）的定义知道它是一个正则图，€币欢ㄊ牵？）的特征值，并且其余的特征值小于大于，因此，我们可以得到 +  + … +  = 。

事实上，是对称矩阵有实特征值，且 =  + ，因此，≤ =  +  +  + … + ，很容易得到 +  +  + … +  = ，双反循环图（，）的特征值为€？  = €？（）， = 0，…，。

定理2.2.双反循环图（，）的特征值为€？  = €？（）， = 1，…，。

3 双反循环图的支撑树的个数

在这一节，我们用（，）表示双反循环图（，）的支撑树的个数。下面我们将要证明双反循环图的支撑树个数的渐进计数定理。

引理3.1.设是循环群，是的子集。如果多项式  （） =  +  + …的根为，，…，，则

（，） =

其中 =  +  + … + 。

证明：由引理1.3和定理2.2，可以得到

（，） = [ €？（）] = []

= [ +  + … +          …   ]

= [（） + （） + … + （） ]

= （）[ +  + … + ]

= （） （）

因为（） =                                                       （4）

其中 = 1时，（） = 。

由 （）的定义和等式（4），我们能够得到

（，） = （） （）

= （）（）…（）

= （）（）…（）

=  =

证毕。

引理3.2.设 （） =  +  + …，则 （）的根满足∣∣>1， = 1，2，…，。

证明：根据 （）的定义容易看出 （1）≠0和（） （） =  +  + … +   + 。

对≠1，我们有

+  + … +  =                                     （5）

如果∣∣<1，则

∣ +  + … + ∣≤∣∣+∣∣+ … +∣∣<

这与等式（5）矛盾，因此有∣∣≥1。

因为≠1，如果∣∣= 1，则可以得到

由（5）式，当 =  + ， 有

+  + … +   =

因此， = 1， （ = 1，2，…，），这与（1，2，…，）矛盾。

当 = 时， +  +  + … +≠。因此，我们有∣>1∣， = 1，2，…，。证毕。

定理3.3.设（，）是点数为的正则双反循环图，则（，） ，

证明： 设（） = ，，（下转第59页）（上接第29页）

，… = ，

则有（） =  + … + 。

设 = 1，可得

（） = 1 +  + … + 。

由（）的定义，设 = 0，则

（1） = … = 。

因此，（） = ，由引理3.2，∣∣>1， = 1，2，…， + ，

可以得到→0， →，对 <。

由引理3.1和上面的式子，有

=

=    + … +

证毕。

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

参考文献

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

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

[3] Matt Devos，Luis Goddyn，Bojan Mohar，Robert Samal，Cayley sum graphs and eigenvalues of （3， 6）-fullerenes， Journal of Combinatorial Theory， Series B 99.2009：358-369.

[4] M.Amooshahi， B.Taeri，Cayley sum color and anti-circulant graphs， Linear Algebra and its Applications， 466.2015：409-420.