循環(huán)圖的距離譜半徑的上界*

周后卿

(邵陽學(xué)院數(shù)學(xué)系，湖南 邵陽 422000)

循環(huán)圖的距離譜半徑的上界*

周后卿

(邵陽學(xué)院數(shù)學(xué)系，湖南 邵陽 422000)

圖G的距離譜半徑μ(G)是指圖G的距離矩陣D(G)的最大特征值。利用循環(huán)圖的直徑，討論了幾類循環(huán)圖的距離譜半徑，得出了它們的上界；并且討論了循環(huán)圖的卡氏積圖的距離譜半徑的上界。

循環(huán)圖；距離譜半徑；直徑；卡氏積圖

設(shè)G是一個(gè)簡(jiǎn)單的連通圖，頂點(diǎn)集為V(G)={v1,v2,…,vn}。G的距離矩陣D=D(G)由元素dij組成，dij表示頂點(diǎn)vi到頂點(diǎn)vj的距離(即從頂點(diǎn)vi到頂點(diǎn)vj的一條最短路)。D(G)的特征值又叫G的D特征值，因?yàn)榫嚯x矩陣D是一個(gè)實(shí)對(duì)稱矩陣，所以，它的特征值μi(i=1,2,…,n)全是實(shí)數(shù)，不妨設(shè)為μ1≥μ2≥…≥μn。把距離矩陣D的最大特征值μ1(簡(jiǎn)記為μ)叫做G的距離譜半徑。兩個(gè)圖若具有相同的距離譜,則稱它們是D-共譜圖。正如我們所知, 一個(gè)圖的所有拓?fù)湫畔⒖梢詮乃泥徑泳仃囌业?。圖譜理論研究圖的性質(zhì)和它相應(yīng)矩陣的譜之間的關(guān)系，如鄰接矩陣、拉普拉斯矩陣和距離矩陣。特別是，圖的一些重要的拓?fù)湫畔⒖梢詮钠涮囟ǖ奶卣髦?第一個(gè)或最大的一個(gè)) 提取到，從整個(gè)圖譜中閱讀信息的方法在文獻(xiàn)[1-2]中有過探索。盡管存在同譜圖，通過快速計(jì)算算法及其與圖的構(gòu)造之間密切關(guān)系，譜圖可提供一種方法去解決(子)圖同構(gòu)問題。圖的距離矩陣在許多領(lǐng)域都有應(yīng)用，譬如通訊網(wǎng)絡(luò)設(shè)計(jì)，圖的嵌入理論，分子穩(wěn)定性，網(wǎng)絡(luò)流算法等[3-4]。Balaban等[5]提議在廣泛的QSPR研究中將距離譜半徑作為分子描述符；文獻(xiàn)[6]將譜半徑用于推斷分子范圍和烷烴類模型的沸點(diǎn)的量。

1 背景知識(shí)

循環(huán)圖具有很好的性質(zhì),它是點(diǎn)可遷的。某些網(wǎng)狀互聯(lián)網(wǎng)絡(luò)實(shí)質(zhì)上就是循環(huán)圖對(duì)應(yīng)的網(wǎng)絡(luò),對(duì)循環(huán)圖的網(wǎng)絡(luò)應(yīng)用研究有很多文獻(xiàn)[12-13]。在過去20年里，循環(huán)圖不斷出現(xiàn)在編碼理論，VLSI設(shè)計(jì)，Ramsey理論，并行計(jì)算和分布式計(jì)算中[14-15]。整循環(huán)圖具有高度對(duì)稱性，在連接圖論與數(shù)論之間具有某些卓越的性質(zhì)。在量子通信方案中,循環(huán)圖用于具有N個(gè)相互作用的量子比特的安排問題[16]。

則根據(jù)文獻(xiàn)[17]，A的特征值為

由于循環(huán)圖的距離矩陣D也是一個(gè)循環(huán)矩陣。因此，循環(huán)圖的距離特征值為

(1)

這里,dj表示距離矩陣D的第一行元素。圖的直徑是指圖中任何兩個(gè)頂點(diǎn)之間的最大距離。

設(shè)G=(V(G),E(G)),H=(V(H),E(H))是兩個(gè)簡(jiǎn)單的連通圖，定義G與H的卡氏積(Cartesianproduct) 圖(用G×H表示)：

頂點(diǎn)集為V(G×H)=V(G)×V(H)

其中任何兩個(gè)頂點(diǎn) (u,u′),(v,v′)相鄰當(dāng)且僅當(dāng)u=v且u′,v′在H中相鄰；或u′=v′且u,v在G中相鄰,這里u,v∈V(G),u′,v′∈V(H)。

研究卡氏積圖不僅具有理論意義而且具有實(shí)際應(yīng)用價(jià)值，它是由小規(guī)模網(wǎng)絡(luò)構(gòu)造大規(guī)模網(wǎng)絡(luò)的重要方法，具有很好的連通性、抗毀性。

2 引理與結(jié)論

在證明定理之前，先了解表1。

表1 部分3-循環(huán)圖的直徑、距離譜半徑

從表1可看出，循環(huán)圖的距離譜半徑隨頂點(diǎn)n的增加而增加，與循環(huán)圖的直徑有關(guān)，直徑越大，距離譜半徑也越大。為了證明本文的結(jié)論，還需要下列引理。

對(duì)于兩個(gè)圖的卡氏積圖的特征值，在Cvetkovi′c等的著作《Spectraofgraphs,Theoryandapplications》中有下列結(jié)論。

這里pi,qj分別表示特征值λi，μj的重?cái)?shù)。

對(duì)于整循環(huán)圖，有下列結(jié)論。

引理4[20]在整循環(huán)圖C(n，S)中,直徑d≤2ω(n)+1，其中ω(n)表示n的素因子數(shù)目。

現(xiàn)在證明本文的定理。

其中 4+n1+n2+…+nl=n-1,ni∈Ν+,這里，Ν+表示正整數(shù)集。證畢。

例如，當(dāng)n=10,m=2時(shí)，上述不等式取等號(hào)。

這里E表示偶數(shù)集。

證明 現(xiàn)在分幾種情形予以討論。

其中 3+4+n1+n2+…+nl=n-1,ni∈Ν+。根據(jù)引理1，得到

上述不等式當(dāng)n=8,s=4時(shí)取等號(hào)。

這里Ο表示奇數(shù)集。

證明 分下列幾種情形討論：

于是，根據(jù)定理2，得到循環(huán)圖G與H的距離譜半徑

再由引理3，得到G與H的卡氏積圖G×H的距離譜半徑為

(0,1,2,…,d1,…,2,1,2,…,d1,…,2,1),

(0,1,2,…,d2,…,2,1,2,…,2,1,2,…,d2,…,2,1)根據(jù)定理2，得到循環(huán)圖G與H的距離譜半徑為

再根據(jù)引理3，得到G與H的卡氏積圖G×H的距離譜半徑為

(0,1,2,…,d1,…,2,1,2,…,2,1,2,…,d1,…,2,1)，

(0,1,2,…,d2,…,2,1,2,…,2,1,2,…,d2,…,2,1)

根據(jù)定理2，得到循環(huán)圖G與H的距離譜半徑分別為

從而由引理3，可得到G與H的卡氏積圖G×H的距離譜半徑為

證畢。

證明 因?yàn)閚=pq,所以n的素因子數(shù)目ω(n)=2。由n的正約數(shù)組成的集合為Dn={1,p,q}。

i) 設(shè)D={p}?Dn，則S={p,2p,…,(q-1)p}，此時(shí)循環(huán)圖C(n,S)是一個(gè)度為q-1的整循環(huán)圖。因此它的距離矩陣的第一行元素包含q-1個(gè)1，由引理4可知,它的直徑d≤5。于是，可推出整循環(huán)圖的距離譜半徑為

n3×4+n4×5,n1+n2+n3+n4=n-q

ii) 設(shè)D={p,q}?Dn，則

此時(shí)循環(huán)圖C(n,S)是一個(gè)度為p+q-2的整循環(huán)圖。因此它的距離矩陣的第一行元素包含p+q-2個(gè)1,由引理4可知,它的直徑d≤5。因此,整循環(huán)圖的距離譜半徑為

n2×3+n3×4+n4×5,

n1+n2+n3+n4=n+1-p-q

iii) 設(shè)D={1,p}?Dn，則

S=Gn(1)∪Gn(p)=

{1,2,…,p,(p+1),…,k,…,pq-1}

k≠q,2q,…,(p-1)q。此時(shí)循環(huán)圖C(n,S)是一個(gè)度為n-p的整循環(huán)圖。它的距離矩陣的第一行元素包含n-p個(gè)1，依據(jù)引理4，它的直徑d≤5。這樣，推出整循環(huán)圖的距離譜半徑為

n3×4+n4×5,n1+n2+n3+n4=p-1

[1]BANERJEEA,JOSTJ.Graphspectraasasystematictoolincomputationalbiology[J].DiscreteAppliedMathematics, 2009,157(10): 2425-2431.

[2]LIUS.Multi-waydualCheegerconstantsandspectralboundsofgraphs[J].AdvancesinMathematics, 2015, 268:306-338.

[3]BOSES,NATHM,PAULS.Distancespectralradiusofgraphswithrpendentvertices[J].LinearAlgebraanditsApplications, 2011, 435: 2828-2836.

[4]YUGL,ZHANGHL,SHUJL.Somegrafttransformationsanditsapplicationsonthedistancespectralradiusofagraph[J].AppliedMathematicsLetters, 2012, 25(3): 315-319.

[5]BALABANAT,CIUBOTARIUD,MEDELEANUM.Topologicalindicesandrealnumbervertexinvariantsbasedongrapheigenvaluesoreigenvectors[J].JournalofChemicalInformationandModeling, 1991, 31:517-523.

[6]GUTMANI,MEDELEANUM.Onthestructure-dependenceofthelargesteigenvalueofthedistancematrixofanalkane[J].IndianJournalofChemistry(SecA)， 1998, 37:569-573.

[7]INDULALG.Sharpboundsonthedistancespectralradiusandthedistanceenergyofgraphs[J].LinearAlgebraanditsApplications, 2009, 430: 106-113.

[8]STEVANOVICD,ILICA.Distancespectralradiusoftreeswithfixedmaximumdegree[J].ElectronicJournalofLinearAlgebra, 2010, 20:168-179.

[9]WANGYN,ZHOUB.Ondistancespectralradiusofgraphs[J].LinearAlgebraanditsApplications, 2013, 438: 3490-3503.

[10]YUG,WUY,SHUJ.Somegrafttransformationsanditsapplicationonadistancespectrum[J].DiscreteMathematics, 2011, 11: 2117-2123.

[11]GUTMANI,INDULALG.Onthedistancespectraofsomegraphs[J].MathematicalCommunications, 2008, 13: 123-131.

[12]NABI-ABDOLYOUSEFIM,MESBAHIM.Onthecontrollabilitypropertiesofcirculantnetworks[J].AutomaticControl,IEEETransactionson, 2013, 58 (12):3179-3184.

[13]SHEELAD,ABINAYAS,ANGELOVG.Performanceevaluationofsurvivabilityinopticalnetworksbasedongraphtheory[J].InternationalJournalofScientific&EngineeringResearch, 2014, 5(4): 2229-2253.

[14]RADZISZOWSKISP.SmallRamseynumbers(Revision#14) [J].ElectronicJCombinatorics,DynamicSurvey1, 2014: 1-94.

[15]LINDSAYM,CAINJW.ImprovedlowerboundsontheclassicalRamseynumbersR(4; 22)andR(4; 25) [J].http:∥arxiv.org/pdf/1510.06102, 2015.

[16]MILANBASIC.Characterizationofquantumcirculantnetworkshavingperfectstatetransfer[J].QuantumInformationProcessing, 2013, 12(1): 345-364.

[17]DAVISPJ.Circulantmatrices[M].PureandAppliedMathematics,JohnWiley&sons,NewYork, 1979.

[18]HSUDF,SHAPIROJ.Boundsfortheminimalnumberoftransmissiondelaysindoubleloopnetworks[J].JournalofCombinatorics,InformationandSystemSciences, 1991, 16: 55-62.

[19]MEIJERPT.Connectivitiesanddiametersofcirculantgraphs[D].SimonFraserUniversity,1991.

[20]STEVANOVICD,PETKOVICM,BASICM.Onthediameterofintegralcirculantgraphs[J].ArsCombinatoria, 2012,106: 495 -500.

Upper bounds of distance spectral radius for circulant graphs

ZHOUHouqing

(Department of Mathematics, Shaoyang University, Shaoyang 422000, China )

The distance spectral radiusμ(G)ofagraphGisthelargesteigenvalueofthedistancematrixD(G).Byusingdiameterofcirculantgraphs,someupperboundsforμ(G)areobtained.Furthermore,theupperboundofCartesianproductgraphforcirculantgraphsarediscussed.

circulant graph;distance spectral radius; diameter; Cartesian product graph

10.13471/j.cnki.acta.snus.2016.02.004

2015-11-12

湖南省教育廳科學(xué)研究資助項(xiàng)目(15C1235)；邵陽市科技局科技計(jì)劃資助項(xiàng)目(2015JH41)

周后卿(1963年生)，男；研究方向: 圖論和組合數(shù)學(xué);E-mail:zhouhq2004@163.com

O

A

0529-6579(2016)02-0018-06