兩類特殊圖的距離譜

賈會(huì)才， 胡李寧

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

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

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

中圖分類號(hào)：O157.5 文獻(xiàn)標(biāo)志碼：A

收稿日期：2015-05-25

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

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

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

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

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

(1)圖G的頂點(diǎn)或結(jié)點(diǎn)v1,v2,…,vn組成頂點(diǎn)集，記作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)的特征值及其特征值的重?cái)?shù)構(gòu)成了圖G的距離譜.

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

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

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

圖1　圖G 1 Fig.1　Graph G 1

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

2.1圖的距離矩陣表示

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

2.2圖的距離譜求解

證明 經(jīng)過計(jì)算

圖2　圖G 2 Fig.2　Graph G 2

3團(tuán)每個(gè)點(diǎn)都連一些懸掛點(diǎn)的圖的距離譜問題

圖G2如圖2所示,中心團(tuán)每個(gè)點(diǎn)都連一些懸掛點(diǎn).

3.1圖的距離矩陣表示

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

3.2圖的距離譜求解

證明經(jīng)過計(jì)算

參考文獻(xiàn)：

[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