魯文鼎，葉永升，孫威

（1.淮北師范大學數(shù)學科學學院，安徽淮北235000；2.安慶師范大學數(shù)學與計算科學學院，安徽安慶246011）

一類圖的連通補圖的特征值比較

魯文鼎1，葉永升1，孫威2①

（1.淮北師范大學數(shù)學科學學院，安徽淮北235000；2.安慶師范大學數(shù)學與計算科學學院，安徽安慶246011）

圖的特征值在刻畫連通圖的性質時具有重要的作用.文章運用代數(shù)知識計算一類補圖的鄰接矩陣，進而計算該鄰接矩陣的特征多項式.在已有定理基礎上，分析連通補圖的特征多項式的特征值，給出該連通補圖的特征值比較.

鄰接矩陣；特征值；補圖；比較

0 引言

設A是n×n的矩陣，E是與A同階的單位矩陣，則λE-A稱為A的特征矩陣，||λE-A為A的特征多項式.設G是一個簡單圖，則圖G的鄰接矩陣記為，其中，當vi，vj相鄰時，aij=1，否則圖的特征值指的是該圖鄰接矩陣的特征值.特征方程的最小根稱為最小特征值.在圖類中，我們要借助圖的鄰接矩陣及其特征值來研究圖的特性.

1 基礎知識

定義1.1［1］如果，稱圖H為G的子圖.

定義1.2［2］當且僅當兩個頂點不在同一個Vi中，此二頂點相鄰，則稱圖G為完全r部圖，記成

引理1.1［3］設A是一實對稱n×n矩陣，B為A的m×m階主子陣，且λ1（A）≥λ2（A）≥…≥λn（A）以及λ1（B）≥λ2（B）≥…≥λm（B）分別為A和B的特征值.則對于i=1，2，…，m，有

在文獻［4］中，設G=（V，E）為n階簡單圖.對于向量X∈Rn，如果存在一個從V到X中對應值的映射φ，使得對于任意的u∈V有Xu=φ（u），則稱X定義在G上.因此有

設λ是A（G）對應于特征向量X的特征值，當且僅當X≠0且對每個v∈V（G），有

目前，學者試圖找到計算特殊圖類特征值的方法，文獻［5］給出無符號的拉普拉斯樹的補圖的特征值計算.此外，張恭慶［6］等對于求譜半徑（最大特征值）的算法作了研究.

2 特征值的比較

定義2.1設KP和Kq為兩個不交的完全圖，u，v分別是KP與Kq中的點，，而點A和B是Kq的兩個分別被點C和D固定的懸掛點，連接u，v所得的圖記為G（p，q，1，2）.

定理2.1給定一個正整數(shù)n（n≥10），對于任意的正整數(shù)p和q滿足p≥3，q≥1且p+q=n，p≥q≥1時，有

這個矩陣有n+2行n+2列.則有

令

此時，0不是最小特征值且-1也不是最小特征值.不妨設λ′1是最小特征值，故

即λ′1為fmin（）λ的最小根.為便于討論，記

情形2：當q=2時，在原圖的Kq部分，v點要么與C點重合，要么與D點重合，由對稱性，不妨考慮v點與C點重合的情況.

顯然，在補圖中，D點除了與B點和C點不相鄰外與其余的點都相鄰，C點除了與D點、A點和u1點不相鄰外與其余的點都相鄰，A點除了與C點不相鄰外與其余的點都相鄰，B點除與D點不相鄰外與其余點都相鄰.此外，u2，u3，…，un-2只與C、D、A、B四點相鄰，u1只與D、A、B三點相鄰.故連通補圖的鄰接矩陣

這個矩陣有n+2行n+2列.則

設最小特征值為λ′2，此時

這里

對于λ≤-8時，顯然有

情形3：當q≥3時，顯然GC（）p，q，1，2為連通的非完全圖，由引理1.1可知，故

作為下面討論的引入，我們設X是GC（p，q，1，2）的第一特征向量，由文獻［4］的特征等式（1.2）的結果，在Kp內的所有點除u1外，在X中對應著相同的值，即u2，u3，…，up所對應的特征向量的各個分量相同.

不妨設Kp內所有點除u1外在X中對應的特征分量為X1且在Kq內所有點除C、D、V外在X中都對應相同的值，記為X4.再設Xu1=X2，X3=XV，X5=XC，X6=XD.

事實上，XC與XD對應的特征分量是不同的，這是因為λXC=（p-1） X1+X2+XB，λXD=（p-1） X1+X2+XA，又XA不一定等于XB，故XC≠XD（λ≠0）.在補圖中，A點與KP內所有的點均相鄰，B點均與KP內所有的點相鄰，又因為補圖中A點與D點相鄰，B點與C點相鄰，則XC不一定等于XD，故將記XA=X7，XB=X8.

此外，在連通補圖中，X1中存在u2點與Kq中點點相鄰；u1與v點不相鄰，故X2與Kp內除了V點外所有的點均相鄰；X3在Kq內，Kq中對應的V點與C點、D點都不相鄰，同時與Kq內所有的點都不相鄰；除v點外，Kq內其他的點與Kp中的對應點均相鄰；C點與Kp中所有的點都相鄰且與B點相鄰，但它與A點不相鄰；D點與Kp中所有的點都相鄰且與A點相鄰，但它與B點不相鄰；A點與C點不相鄰；B點與D點不相鄰，則有

將上述的等量關系表達式轉換成矩陣等式

在畜牧業(yè)生產過程中，會產生大量的危害因素，不僅為生態(tài)環(huán)境帶來負擔，還影響了我國畜牧業(yè)的生產與發(fā)展?；诖耍挥腥嬲莆粘Ｒ姷纳a污染摸，積極制定解決措施，以此降低畜牧業(yè)生產污染，保護我國生態(tài)環(huán)境，推動畜牧業(yè)可持續(xù)發(fā)展。對此，下文對畜牧業(yè)常見的生產污染展開探討。

記

則

子情況（1）：

令

令

子情況（2）：當q≥p+11時，由上述證明有

故對q≥3時的情形，有

由于q=1時的最小特征值比q=2時的最小特征值要大，記q=1時的最小特征值是λ′1，則它是的根；記q=2時的最小特征值是λ′2，則它是的根.因為

故比較q=3和q=2時的特征值.

設q=3與q=2時，對應的特征多項式分別為F1（）x和F2（）x，則

記

故

［1］TUTTE W T.Graph Theory［M］.北京：機械工業(yè)出版社，2004.

［2］王樹和.圖論［M］.北京：科學出版社，2011.

［3］HAEMERS W.Interlacing eigenvalue and graphs［J］.Linear Algebra Appl，1995，227：593-616.

［4］FIEDLERM.A property of eigenvectors of nonegative symmetric matrices and its application to graph theory［J］.Czech Math J，1975，25：619-633.

［5］LI S C，WANG S J.The least eigenvalue of the signless Laplacian of the complements of tree［J］.Linear Algebra Appl，2012，436：2398-2405.

［6］CHANG K C，PEARSON K，ZHANG T.Primitivity，the convergence of the NZQ method，and the largest eigenvalue for non?egative tensors［J］.SIAM J Matrix Anal Appl，2011，32：806-819.

The Comparison of Eigenvalue of the Graph with Two Leaves and Complement Connected

LU Wending1，YE Yongsheng1，SUN Wei2
（1.School of Mathematical Sciences，Huaibei Normal University，235000，Huaibei，Anhui，China；2.School of Mathematics and Computation Sciences，Anqing Normal University，246011，Anqing，Anhui，China）

The characteristic value of the graph has the important function in recording the properties of the connected graphs.This essay calculated the adjacency matrix of some graphs by using algebraic knowledge. What is more，it also calculated the characteristic polynomial of the adjacency matrix.Based on the fundamen?tal of the theorem recently，the essay analyzed the characteristic value of characteristic polynomial on the con?nected and complementary graphs，and compared the characteristic value of the connected and complementa?ry graphs.

adjacency matrix；eigenvalue；complementary graph；comparison

O 157.5

A

2095-0691（2016）03-0016-05

2016-04-18

安徽省自然科學基金項目（1408085MA08）；安徽省高校自然科學基金項目（KJ2016A633）

魯文鼎（1991-），男，安徽當涂人，碩士生，研究方向為圖論及其應用；通訊作者：葉永升（1964-），男，安徽嘉山人，教授，主要從事圖論及其應用研究.