无爪图的谱半径与可迹性

谢兆丰，周　甫，叶淼林

(安庆师范学院 数学与计算科学学院，安徽 安庆 246133)



无爪图的谱半径与可迹性

谢兆丰，周甫，叶淼林

(安庆师范学院 数学与计算科学学院，安徽 安庆 246133)

摘要：针对无爪图，将谱半径与稳定性相结合，得出了其关于可迹性判定的两个结论。此结论又利用图与补图的谱半径分别刻画无爪连通图是可迹图的充分条件，并利用一系列引理及代数方法加以证明，部分结论优于前人的成果。

关键词：代数图论；可迹性；谱半径；无爪图

判断一个图的可迹性是图论中一个富有魅力而又十分困难的问题[1]。通过代数方法，尤其是谱方法加以研究，是解决这个问题的可能方向之一，前人对此多有探索[2-11]。而对一般图的可迹性，Bo Ning和Binlong Li[12]对无爪图的可迹性进行了研究，本文通过类似的方法，在其基础上进一步加以探索，并改进了部分结论。

先介绍一些相关记号、概念和引理等。

如果图G中任意两点间均有一条路连接，则称G是连通的。 如果图G中的一条路包含G中所有的顶点，则称这条路为哈密顿路；如果图G含有哈密顿路，则称G为可迹图。 如果图G中的一个圈包含G中所有的顶点，则称这条路为哈密顿圈；如果图G含有哈密顿圈，则称G为哈密尔顿图。

文章中所讨论的图均为无向简单图。设G=[V(G),E(G)]为n阶无向简单图，顶点集合V(G)={v1,v2，…,vn}。记图的边数e(G)=

接下来介绍闭包的概念。对于非负整数k，若选取图G中度数和不小于k的不相邻点对加以连接，反复选取连接直到没有这样的点对存在后，所得的图称为G的k-闭包，记作Ck(G)[13]。 注意到对于Ck(G)中任意不相邻点对u,v，都有dCk(G)(u)+dCk(G)(v)≤k-1。

记L与Nn-3,3为两个特殊图，如图1所示，其中Nn-3,3是通过在Kn-3中3个顶点粘3条悬挂边所构成的图。

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

G=Nn-3,3或L。

引理4[15]设G是n阶图，则G是可迹的，当且仅当Cn-1(G)是可迹的。

引理5[16]设G是n阶图，则

下面给出本文的主要结论。

证明由文献[17]可得

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

结合引理1即得G是可迹的，除非G=Nn-3,3或L。

证明设G有m条边，由引理3可得，

参考文献:

[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

文章编号：1007-4260(2016)01-0008-02

中图分类号：O157

文献标识码：A

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

作者简介：谢兆丰，男，安徽安庆人，安庆师范学院数学与计算科学学院硕士研究生，研究方向为代数图论。E-mail: 2423957714@qq.com

基金项目：安徽省自然科学基金(11040606M14)。

*收稿日期：2015-08-04

网络出版时间：2016-03-15 17:05网络出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160315.1705.003.html