兩類特殊圖的距離譜

兩類特殊圖的距離譜

賈會才， 胡李寧

(河南工程學(xué)院 理學(xué)院，河南 鄭州 451191)

摘要：圖的距離譜問題是指圖的距離矩陣的特征值問題.主要研究了具有特殊結(jié)構(gòu)的兩類圖的距離譜問題，計算了這兩類圖的距離特征多項式，獲得了它們的距離譜,對于研究圖的距離譜確定問題具有重要意義.

關(guān)鍵詞：圖譜理論;距離矩陣;距離譜

中圖分類號：O157.5 文獻標志碼：A

收稿日期：2015-05-25

基金項目：河南省教育廳科學(xué)技術(shù)研究重點項目(13B110939)

作者簡介：賈會才(1981-),男,河南許昌人，講師,主要從事圖論研究.

圖譜理論主要研究圖的鄰接矩陣、拉普拉斯矩陣、無符號拉普拉斯矩陣及距離矩陣等圖的重要矩陣特征值問題，是組合矩陣論和代數(shù)圖論的重要研究領(lǐng)域.圖的距離矩陣經(jīng)常出現(xiàn)在通信網(wǎng)絡(luò)設(shè)計、圖的嵌入設(shè)計、分子穩(wěn)定性及網(wǎng)絡(luò)流算法等領(lǐng)域.距離譜問題在量子化學(xué)、物理學(xué)、計算機科學(xué)、通信網(wǎng)絡(luò)及信息科學(xué)等領(lǐng)域均有廣泛應(yīng)用.目前，圖的距離譜問題主要集中在刻畫給定圖類中圖的距離譜半徑取得最大或者最小的圖[1-4]、圖的距離特征值的分布及圖的距離譜確定問題[5].本課題主要研究了具有特殊結(jié)構(gòu)的兩類圖的距離譜問題，計算了這兩類圖的距離特征多項式，從而獲得了它們的距離譜,對于研究圖的距離譜確定問題具有重要意義.

1基本概念和結(jié)論

定義1圖G是一個三元組，記作G=,其中

(1)圖G的頂點或結(jié)點v1,v2,…,vn組成頂點集，記作V(G)={v1,v2,…,vn}(V(G)≠?) ;

(2)圖G的邊e1,e2,…,em組成的邊集記作E(G)={e1,e2,…,em};

(3)φ(G)：E→V×V稱為關(guān)聯(lián)函數(shù).

定義2圖G的距離矩陣D定義為D=D(G)=(dij)=dG(vi,vj) .

定義3D(G)的特征值及其特征值的重數(shù)構(gòu)成了圖G的距離譜.

定義4設(shè)圖G的距離矩陣為D, 則圖G的距離特征多項式定義為det(λI-D).

參考文獻上述未介紹的符號和術(shù)語可[6].

2中心團與多個懸掛團相連(join)的圖的距離譜問題

圖1　圖G 1 Fig.1　Graph G 1

圖G1(見圖1)：中心團與懸掛團相連(join), 是指中心圖中每一個點與懸掛團中每一個點都連邊.顯然，同一個團內(nèi)點之間的距離為1,中心團與懸掛團的點之間距離為1, 而懸掛團點之間的距離為2.因此，圖G1的直徑為2.

2.1圖的距離矩陣表示

在圖1中，團kn1中的點與團kn2,kn3, …, knk之間的點的距離為1; 團kn2,kn3, …, knk中點之間的距離為2,且有n1+n2+…+nk=n.圖G1的距離矩陣表示為

2.2圖的距離譜求解

證明 經(jīng)過計算

圖2　圖G 2 Fig.2　Graph G 2

3團每個點都連一些懸掛點的圖的距離譜問題

圖G2如圖2所示,中心團每個點都連一些懸掛點.

3.1圖的距離矩陣表示

如圖2所示，團kk中每個點都連一些懸掛點,團內(nèi)第i個點連ni個點.同一個團內(nèi)點之間的距離為1；ni內(nèi)點與團中除第i個點外的其余點之間的距離為2；ni內(nèi)任意兩個不同點之間的距離為2；ni內(nèi)的點與n1,…,ni-1,ni+1,…,nk內(nèi)的點之間距離3.因此,圖G2的直徑為3.距離矩陣可以表示為

3.2圖的距離譜求解

證明經(jīng)過計算

參考文獻：

[1]IlicA.Distancespectralradiusoftreeswithgivenmatchingnumber[J].DiscreteApplicationofMathematics,2010(158):1799-1806.

[2]LinH,YangW,ZhangH.Distancespectralradiusofdigraphswithgivenconnectivity[J].DiscreteMathematics,2012(312):1849-1856.

[3]YuG,WuY,ZhangY.Somegrafttransformationsanditsapplicationonadistancespectrum[J].DiscreteMath,2011(311):2117-2123.

[4]ZhangX.Onthedistancespectralradiusofsomegraphs[J].LinearAlgebraApplication,2012(437):1930-1941.

[5]LinHQ,HongY,WangJF,etal.Onthedistancespectrumofgraphs[J].LinearAlgebraApplication, 2013(439):1662-1669.

[6]BondyJA,MurtyUSR.GraphTheorywithApplications[M].London:MacmillanPublishersLimited,1976.

Distance spectra of two kinds of graphs with special structure

JIA Huicai, HU Lining

(CollegeofSciences,HenanInstituteofEngineering,Zhengzhou451191,China)

Abstract:The problem on the distance spectra of graphs refers to that on the eigenvalues of distance matrix of graphs. This paper mainly investigates the distance spectra of two kinds of graphs with special structure, providing the distance characteristic polynomial and obtaining their distance spectra. This plays an important role to the problem on the distance spectrum characterization of graphs.

Key words:spectral graph theory; distance matrix; distance spectrum