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

許英+王冉冉

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

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

中圖分類號(hào)：O151 文獻(xiàn)標(biāo)識(shí)碼：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è)是一個(gè)有個(gè)點(diǎn)的簡(jiǎn)單圖，點(diǎn)集為 = （） = {，，…，}邊集為 = （）。圖的鄰接矩陣被定義為一個(gè)階矩陣 = （） = []，其中 = 1如果和是相鄰的，否則 = 0。因?yàn)槭菍?shí)對(duì)稱矩陣，所以可以設(shè)的特征值為：（）≤（）≤…≤（）。

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

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

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

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

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

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

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

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

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

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

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

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

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

在這一節(jié)，我們將要談?wù)撾p反循環(huán)圖的特征值。

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

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

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

= ? = ?+ ?+ … +

= ? = ?+ ?+ … +

（1）

其中角標(biāo)都模。

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

= ， = ， = ，…， =

= ， = ， = ，…， =

（2）

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

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

因此，我們可以得到矩陣的特征多項(xiàng)式

（3）

因?yàn)槭鞘仔袨椋ǎ┑姆囱h(huán)矩陣，且

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

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

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

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

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

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

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

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

（，） =

其中 = ?+ ?+ … + 。

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

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

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

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

= （）[ + ?+ … + ]

= （） （）

因?yàn)椋ǎ?= ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （4）

其中 = 1時(shí)，（） = 。

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

（，） = （） （）

= （）（）…（）

= （）（）…（）

= ?=

證畢。

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

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

對(duì)≠1，我們有

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

如果∣∣<1，則

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

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

因?yàn)椤?，如果∣∣= 1，則可以得到

由（5）式，當(dāng) = ?+ ， 有

+ ?+ … + ? =

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

當(dāng) = 時(shí)， + ?+ ?+ … +≠。因此，我們有∣>1∣， = 1，2，…，。證畢。

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

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

，… = ，

則有（） = ?+ … + 。

設(shè) = 1，可得

（） = 1 + ?+ … + 。

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

（1） = … = 。

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

可以得到→0， →，對(duì) <。

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

=

= ? ?+ … +

證畢。

基金項(xiàng)目：新疆財(cái)經(jīng)大學(xué)博士基金項(xiàng)目

參考文獻(xiàn)

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