謝兆豐，周　甫，葉淼林

(安慶師范學(xué)院 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，安徽 安慶 246133)

?

無(wú)爪圖的譜半徑與可跡性

謝兆豐，周甫，葉淼林

(安慶師范學(xué)院 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，安徽 安慶 246133)

摘要：針對(duì)無(wú)爪圖，將譜半徑與穩(wěn)定性相結(jié)合，得出了其關(guān)于可跡性判定的兩個(gè)結(jié)論。此結(jié)論又利用圖與補(bǔ)圖的譜半徑分別刻畫無(wú)爪連通圖是可跡圖的充分條件，并利用一系列引理及代數(shù)方法加以證明，部分結(jié)論優(yōu)于前人的成果。

關(guān)鍵詞：代數(shù)圖論；可跡性；譜半徑；無(wú)爪圖

判斷一個(gè)圖的可跡性是圖論中一個(gè)富有魅力而又十分困難的問(wèn)題[1]。通過(guò)代數(shù)方法，尤其是譜方法加以研究，是解決這個(gè)問(wèn)題的可能方向之一，前人對(duì)此多有探索[2-11]。而對(duì)一般圖的可跡性，Bo Ning和Binlong Li[12]對(duì)無(wú)爪圖的可跡性進(jìn)行了研究，本文通過(guò)類似的方法，在其基礎(chǔ)上進(jìn)一步加以探索，并改進(jìn)了部分結(jié)論。

先介紹一些相關(guān)記號(hào)、概念和引理等。

如果圖G中任意兩點(diǎn)間均有一條路連接，則稱G是連通的。 如果圖G中的一條路包含G中所有的頂點(diǎn)，則稱這條路為哈密頓路；如果圖G含有哈密頓路，則稱G為可跡圖。 如果圖G中的一個(gè)圈包含G中所有的頂點(diǎn)，則稱這條路為哈密頓圈；如果圖G含有哈密頓圈，則稱G為哈密爾頓圖。

文章中所討論的圖均為無(wú)向簡(jiǎn)單圖。設(shè)G=[V(G),E(G)]為n階無(wú)向簡(jiǎn)單圖，頂點(diǎn)集合V(G)={v1,v2，…,vn}。記圖的邊數(shù)e(G)=

接下來(lái)介紹閉包的概念。對(duì)于非負(fù)整數(shù)k，若選取圖G中度數(shù)和不小于k的不相鄰點(diǎn)對(duì)加以連接，反復(fù)選取連接直到?jīng)]有這樣的點(diǎn)對(duì)存在后，所得的圖稱為G的k-閉包，記作Ck(G)[13]。 注意到對(duì)于Ck(G)中任意不相鄰點(diǎn)對(duì)u,v，都有dCk(G)(u)+dCk(G)(v)≤k-1。

記L與Nn-3,3為兩個(gè)特殊圖，如圖1所示，其中Nn-3,3是通過(guò)在Kn-3中3個(gè)頂點(diǎn)粘3條懸掛邊所構(gòu)成的圖。

圖1　L(左)及Nn-3,3(右)圖

G=Nn-3,3或L。

引理4[15]設(shè)G是n階圖，則G是可跡的，當(dāng)且僅當(dāng)Cn-1(G)是可跡的。

引理5[16]設(shè)G是n階圖，則

下面給出本文的主要結(jié)論。

證明由文獻(xiàn)[17]可得

μ[Kk∨(n-k)K1]=

結(jié)合引理1即得G是可跡的，除非G=Nn-3,3或L。

證明設(shè)G有m條邊，由引理3可得，

參考文獻(xiàn):

[1]R.M.Karp.ComplexityofComputerComputations[M].NewYork:Plenum, 1972: 85-103.

[2]M.Fiedler,V.Nikiforov.SpectralradiusandHamiltonicityofgraphs[J].LinearAlgebraanditsApplications, 2010, 432(1): 2170-2173.

[3]BoZhou.SignlessLaplacianspectralradiusandHamiltonicity[J].LinearAlgebraandItsApplications, 2010, 432(2-3): 566-570.

[4]RaoLi.EnergyandsomeHamiltonianpropertiesofgraphs[J].AppliedMathematicalSciences, 2009, 56(3): 2775-2780.

[5]MeiLu,HuiqingLiu,WenfengTian.SpectralradiusandHamiltoniangraphs[J].LinearAlgebraandItsApplications, 2012, 437(7): 1670-1674.

[6]S.Butler,FanChung.SmallspectralgapinthecombinatorialLaplacianimpliesHamiltonian[J].AnnalsComb., 2010, 13(4): 403-412.

[7]YizhengFan,GuidongYu.SpectralconditionforagraphtobeHamiltonianwithrespecttonormalizedLaplacian[EB/OL]. (2012-03-26)[2015-06-06].http://www.paper.edu.cn/releasepaper/content/201203-714.

[8]GuidongYu,YizhengFan.SpectralconditionsforagraphtobeHamilton-connected[J/OL].AppliedMechanicsandMaterials, 2013, 336-338：2329-2334[2015-06-06].DOI: 10.4028/www.scientific.net/AMM.336-338.2329.

[9] Yu Guidong. Spectral conditions for Hamiltonicity of graphs [J]. Mathematica Applicata, 2014, 27(3): 588-595.

[10] Guidong Yu, Miaolin Ye, Gaixiang Cai,et al..Signless Laplacian Spectral conditions for Hamiltonicity of graphs [J/OL]. Journal of Applied Mathematics, 2014: 1-6[2015-06-06]. http://dx.doi.org/10.1155/2014/282053.

[11] Guidong Yu, Gaixiang Cai,Miaolin Ye, et al..Energy conditions for Hamiltonicity of graphs[J/OL].Discrete Dynamics in Nature and Society,2014:1-6[2015-06-06].http://dx.doi.org/10.1155/2014/305164.

[12] Bo Ning, Binlong Li. Spectral radius and traceability of connected claw-free graphs [EB/OL]. (2014-06-27)[2015-06-06]. http://arxiv.org/abs/1406.5404v3.

[13] J.A. Bondy, U.S.R. Mutry. Graph Theory with Applications [M]. New York: Elsevier Science Publishing Co., 1976.

[14] Yuan Hong. Bounds of eigenvalues of graphs[J]. Discrete Mathematics, 1993, 123(1-3): 65-74.

[15] O. Ore. Note on Hamilton circuits [J]. The American Mathematical Monthly, 1960, 67: 55.

[16] M. Hofmeisfer. Spectral radius and degree sequence[J]. Mathematische Nachrichten, 1988,139(1)：37-44.

[17] D. Cvetkovi, M. Doob, H. Sachs. Spectra of Graphs-Theory and Applications[M].New York:Academic, 1980.

Spectral Radius and Traceability of Claw-Free Connected Graphs

XIE Zhao-feng，ZHOU Fu，YE Miao-lin

(School of mathematics and Computing Science, Anqing Teachers College, Anqing，Anhui 246133, China)

Abstract:In this paper, two conclusions are obtained for the determination of the traceability of the claw-free graph, by the way of combining the method of spectral radius and stability. These conclusions are described as the sufficient condition of claw-free connected graph by the spectral radius of graph and complementary graph. Some lemmas are used to prove them, and some conclusions are better than the previous ones.

Key words:Algebraic graph theory，traceability，spectral radius，claw-free graph

文章編號(hào)：1007-4260(2016)01-0008-02

中圖分類號(hào)：O157

文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.13757/j.cnki.cn34-1150/n.2016.01.003

作者簡(jiǎn)介：謝兆豐，男，安徽安慶人，安慶師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院碩士研究生，研究方向?yàn)榇鷶?shù)圖論。E-mail: 2423957714@qq.com

基金項(xiàng)目：安徽省自然科學(xué)基金(11040606M14)。

*收稿日期：2015-08-04

網(wǎng)絡(luò)出版時(shí)間：2016-03-15 17:05網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160315.1705.003.html