反循環(huán)圖的一些代數(shù)性質(zhì)及其推廣

許英+王冉冉

摘 要 一個圖被稱為反循環(huán)圖，如果這個圖的鄰接矩陣是一個反循環(huán)矩陣。在本文中，我們將定義雙反循環(huán)圖，并且給出它的譜，圖的譜是圖的一種重要性征，在物理和化學領(lǐng)域中，通過對物質(zhì)分子所對應的分子圖的譜的研究，可以預知該物質(zhì)在某些物理和化學方面的性質(zhì)，例如，圖的譜與圖所對應化學分子的能量有關(guān)。另外，我們將研究雙反循環(huán)圖的支撐樹個數(shù)的漸進計數(shù)定理，圖的支撐樹數(shù)是圖的重要的不變量，也是網(wǎng)絡(luò)可靠性的重要的量度。

關(guān)鍵詞 Cayley和圖 反循環(huán)圖 支撐樹 譜

中圖分類號：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 引言

設(shè)是一個有個點的簡單圖，點集為 = （） = {，，…，}邊集為 = （）。圖的鄰接矩陣被定義為一個階矩陣 = （） = []，其中 = 1如果和是相鄰的，否則 = 0。因為是實對稱矩陣，所以可以設(shè)的特征值為：（）≤（）≤…≤（）。

設(shè)是一個有限群，是群的子集。的關(guān)于的有向圖 = （，）是一個點集為的有向圖，對，，到有一條弧當且僅當。當是循環(huán)群時，有向圖（，）被稱為一個循環(huán)有向圖。

設(shè)是一個有限群，是群的子集，我們用（）表示的關(guān)于的和圖，和圖（）是一個無向圖，點集為，邊集為{（，） €？： + }。如果存在使得，則邊（，）是一個半邊：半邊是只有一個端點的邊。

關(guān)于和圖的研究成果已經(jīng)有很多，例如，和圖的哈密爾頓圈; 和圖的獨立數(shù)。和圖的直徑與特征值之間的關(guān)系;和圖的團數(shù);和圖的連通度。在文獻[4]中，M.Amooshahi等人定義了反循環(huán)圖并且研究了反循環(huán)圖的一些性質(zhì)，另外，他們還證明了一個圖是反循環(huán)圖當且僅當它是一個循環(huán)群上的和圖。

反移位作用 ：→定義為（，，…，） = （，，…，，）。反循環(huán)矩陣是一個關(guān)于向量 = （，，…，）的 €？矩陣，它的行是由反移位作用來確定，也就是，第行是， = 1，2，…，。

一個有個點的圖被稱為反循環(huán)圖，如果它有反循環(huán)鄰接矩陣，即 = []（）是反循環(huán)矩陣，當且僅當 = 對所有的。

類似于雙循環(huán)圖，我們定義雙反循環(huán)圖。設(shè)是循環(huán)群，是的子集，雙反循環(huán)圖（，）是一個二部圖，點集為 ?€？{0，1}邊集為{{（，0），（，1）}：，}，很容易可以看到雙反循環(huán)圖（，）是一個點數(shù)為2的正則圖。在本文中，我們將討論雙反循環(huán)圖的譜和它的支撐樹個數(shù)的漸進定理。

下面，我們引入幾個在下一節(jié)需要用到的已知結(jié)果。

引理1.1 （Horn [1]）.設(shè)，，，是 €？矩陣，且∣∣≠ 0， ?= ，則。

設(shè)表示首行為[0，1，0，…，0]的循環(huán)矩陣。

引理1.2 （Biggs [2]）.設(shè) = （，）是一個循環(huán)圖。則的鄰接矩陣是 = ，的特征值為 = ， = 0，1，…， ，其中 = （/），注意{ ： 0≤≤}是方程 = 1的所有的解，它們被稱為次單位根。

引理1.3 （Biggs [2]）.設(shè)是一個連通正則圖，它的譜為

則的支撐樹的個數(shù)為（） = 。

2 雙反循環(huán)圖的譜

在這一節(jié)，我們將要談論雙反循環(huán)圖的特征值。

引理2.1.設(shè)，是 €？的反循環(huán)矩陣，首行元素是0或者1，則是一個循環(huán)矩陣。

證明：設(shè)反循環(huán)矩陣 = （）， = （），矩陣，的乘積 = ?= （）

根據(jù)矩陣乘積的定義，我們有

= ? = ?+ ?+ … +

= ? = ?+ ?+ … +

（1）

其中角標都模。

由于和都是反循環(huán)矩陣，即，

= ， = ， = ，…， =

= ， = ， = ，…， =

（2）

由（1）（2）兩式，我們很容易可以看出 = ，這意味著矩陣是一個循環(huán)矩陣。

設(shè)雙反循環(huán)圖（，）的鄰接矩陣為，是反循環(huán)圖（）的鄰接矩陣。由雙反循環(huán)圖的定義，很容易可以看出。

因此，我們可以得到矩陣的特征多項式

（3）

因為是首行為（，，，…，）的反循環(huán)矩陣，且

由引理2.1， = 是循環(huán)矩陣，首行為（，，…，）。為了表示出的首行元素，我們設(shè)反循環(huán)集 = ，構(gòu)造集合 = （模），（ = 1，2，…，），即中的每一個元素都減1，我們就得到了集合。設(shè) = ∣∣= ， ?=∣∩∣，…， =∣∩∣，則我們可以得到 = ， ?= ， ?= ，…， = ，由于是一個循環(huán)矩陣，則 = ，因此可以得到的特征值為 = ， = 0，1，2，…，。

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

又根據(jù)雙反循環(huán)圖（，）的定義知道它是一個正則圖，€幣歡ㄊ牽？）的特征值，并且其余的特征值小于大于，因此，我們可以得到 + ?+ … + ?= 。

事實上，是對稱矩陣有實特征值，且 = ?+ ，因此，≤ = ?+ ?+ ?+ … + ，很容易得到 + ?+ ?+ … + ?= ，雙反循環(huán)圖（，）的特征值為€？ ?= €？（）， = 0，…，。

定理2.2.雙反循環(huán)圖（，）的特征值為€？ ?= €？（）， = 1，…，。

3 雙反循環(huán)圖的支撐樹的個數(shù)

在這一節(jié)，我們用（，）表示雙反循環(huán)圖（，）的支撐樹的個數(shù)。下面我們將要證明雙反循環(huán)圖的支撐樹個數(shù)的漸進計數(shù)定理。

引理3.1.設(shè)是循環(huán)群，是的子集。如果多項式 ?（） = ?+ ?+ …的根為，，…，，則

（，） =

其中 = ?+ ?+ … + 。

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

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

= [ + ?+ … + ? ? ? ? ?… ? ]

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

= （）[ + ?+ … + ]

= （） （）

因為（） = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （4）

其中 = 1時，（） = 。

由 （）的定義和等式（4），我們能夠得到

（，） = （） （）

= （）（）…（）

= （）（）…（）

= ?=

證畢。

引理3.2.設(shè) （） = ?+ ?+ …，則 （）的根滿足∣∣>1， = 1，2，…，。

證明：根據(jù) （）的定義容易看出 （1）≠0和（） （） = ?+ ?+ … + ? + 。

對≠1，我們有

+ ?+ … + ?= ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （5）

如果∣∣<1，則

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

這與等式（5）矛盾，因此有∣∣≥1。

因為≠1，如果∣∣= 1，則可以得到

由（5）式，當 = ?+ ， 有

+ ?+ … + ? =

因此， = 1， （ = 1，2，…，），這與（1，2，…，）矛盾。

當 = 時， + ?+ ?+ … +≠。因此，我們有∣>1∣， = 1，2，…，。證畢。

定理3.3.設(shè)（，）是點數(shù)為的正則雙反循環(huán)圖，則（，） ，

證明： 設(shè)（） = ，，（下轉(zhuǎn)第59頁）（上接第29頁）

，… = ，

則有（） = ?+ … + 。

設(shè) = 1，可得

（） = 1 + ?+ … + 。

由（）的定義，設(shè) = 0，則

（1） = … = 。

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

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

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

=

= ? ?+ … +

證畢。

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

參考文獻

[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.