可迹图的谱充分条件

doi:10.15960/j.cnki.issn.1007-6093.2017.01.012

运筹学学报

可迹图的谱充分条件

余桂东^1,* 周甫¹ 刘琦¹

1. 安庆师范大学数学与计算科学学院, 安徽安庆 246133

收稿日期:2016-06-06 出版日期:2017-03-15 发布日期:2017-03-15
通讯作者: 余桂东 guidongy@163.com
基金资助:
安徽省自然科学基金(No. 11040606M14), 安徽省高校自然科学基金(No. KJ2015ZD27)

Spectral sufficient conditions on traceable graphs

YU Guidong^1,* ZHOU Fu¹ LIU Qi¹

1. School of Mathematics and Computation Sciences, Anqing Normal University, Anqing 246133, Anhui China

Received:2016-06-06 Online:2017-03-15 Published:2017-03-15

摘要/Abstract

摘要：

设G是一个简单图, A(G), Q(G)以及Q(G)分别为G的邻接矩阵, 无符号拉普拉斯矩阵以及距离无符号拉普拉斯矩阵, 其最大特征值分别称为G的谱半径, 无符号拉普拉斯谱半径以及距离无符号拉普拉斯谱半径. 如果图G中有一条包含G中所有顶点的路, 则称这条路为哈密顿路; 如果图G含有哈密顿路, 则称G为可迹图; 如果图G含有从任意一点出发的哈密顿路, 则称G从任意一点出发都是可迹的. 主要研究利用图G的谱半径, 无符号拉普拉斯谱半径, 以及距离无符号拉普拉斯谱半径, 分别给出图G从任意一点出发都是可迹的充分条件.

关键词: 从任意一点出发都是可迹的, 谱半径, 无符号拉普拉斯谱半径, 距离无符号拉普拉斯谱半径

Abstract:

Let G be a simple graph, A(G), Q(G) and Q(G) are the adjacency matrix, the signless Laplacian matrix, and the distance signless Laplacian matrix of G, respectively. The largest eigenvalues of A(G), Q(G) and Q(G) are called the spectral radius, the signless Laplacian spectral radius and the distance signless Laplacian spectral radius of G, respectively. A path is called a Hamilton path if it contains all vertices of G. A graph is traceable if it contains a Hamilton path. A graph is traceable from every vertex if it contains a Hamilton path from every vertex. The main research of this paper is to give some sufficient conditions for a graph to be traceable from every vertex in terms of spectral radius, signless Laplacian spectral radius and distance signless Laplacian spectral radius of the graph, respectively.

Key words: traceable from every vertex, spectral radius, signless Laplacian spectral radius, distance signless Laplacian spectral radius

余桂东, 周甫, 刘琦. 可迹图的谱充分条件[J]. 运筹学学报, doi: 10.15960/j.cnki.issn.1007-6093.2017.01.012.

YU Guidong, ZHOU Fu, LIU Qi. Spectral sufficient conditions on traceable graphs[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2017.01.012.

参考文献

[1] Fiedler M, Nikiforov V. Spectral radius and Hamiltonicity of graphs [J]. Linear Algebra Appl., 2010, 432: 2170-2173.

[2] Zhou B. Signless Laplacian spectral radius and Hamiltonicity [J]. Linear Algebra Appl., 2010, 432: 566-570.

[3] Li R. Energy and some Hamiltonian properties of graphs [J]. Applied Mathematical Sciences, 2009, 3: 2775-2780.

[4] Butler S, Chung F. Small spectral gap in the combinatorial Laplacian implies Hamiltonian [J]. Annals Comb., 2010, 13: 403-412.

[5] Lu M, Liu H Q, Tian F. Spectral radius and Hamiltonian graphs [J]. Linear Algebra Appl., 2012, 437: 1670-1674.

[6] Fan Y Z, Yu G D. Spectral condition for a graph to be Hamiltonian with respect to normalized Laplacian [EB/OL]. [2013-10-24]. http://www.paper.edu.cn/en releasepaper/pdf/.

[7] Yu G D, Fan Y Z. Spectral conditions for a graph to be Hamilton-connected [J]. Applied Mechanics and Materials, 2013, 336-338: 2329-2334.

[8] Yu G D, Ye M L, Cai G X, et al. Signless Laplacian Spectral Conditions for Hamiltonicity of Graphs [J]. Journal of Applied Mathematics, 2014, Article ID 282053, 6 pages.

[9] Yu G D, Cai G X, Ye M L, et al. Energy conditions for Hamiltonicity of graphs [J]. Discrete Dynamics in Nature and Society, 2014, Article ID 305164,6 pages.

[10] 余桂东. Spectral Radius and Hamiltonicity of a Graph [J]. 应用数学, 2014, 27: 131-138.

[11] Ning B, Li B. Spectral radius and traceability of connected claw-free graphs [J]. Mathematics, 2014, 2015(2): 1-8.

[12] 李乔. 矩阵论八讲 [M]. 上海：上海科学技术出版社, 1988.

[13] Cvetkovi\'c D, Rowlinson P, Simi\'c S K. signless Laplacians of finite graphs [J]. Linear Algebra Appl., 2007, 423(1): 155-171.

[14] Hong Y. A bound on the spectral radius of graphs in terms of genus [J]. Journal of Combinatorial Theory, 1998, 74: 153-159.

[15] Feng L H, Yu G H. On three conjectures involving the signless Laplacian spectral radius of graphs [J]. Publ. Inst. Math. (Beograd), 2009, 85: 35-38.

[16] Xing R D, Zhou B, Li J P. On the distance signless Laplacian spectral radius of graphs [J]. Linear and Multilinear Algebra. 2014, 62: 1377-1387.

[17] Bondy J A, Murty U S. Graph Theory [M]. Grad.Texts in Math.vol.244, Springer, New York, 2008.

可迹图的谱充分条件

Spectral sufficient conditions on traceable graphs

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

[1]	陈媛媛, 王国平. 三圈图的无符号拉普拉斯谱半径[J]. 运筹学学报, 2019, 23(1): 81-89.
[2]	李浙宁，凌晨，王宜举，杨庆之. 张量分析和多项式优化的若干进展[J]. 运筹学学报, 2014, 18(1): 134-148.
[3]	陈艳, 袁西英, 韩苗苗. 关于三圈图的拉普拉斯谱半径的一些结果[J]. 运筹学学报, 2011, 15(4): 1-8.
[4]	陈琳黄琼湘. 给定顶点数和边数的连通图的Q-谱半径的界[J]. 运筹学学报, 2011, 15(3): 19-28.
[5]	陈琳, 黄琼湘. 给定顶点数和边数的连通图的Q-谱半径[J]. 运筹学学报, 2011, (3): 19-28.
[6]	吴廷增, 扈生彪. m重似星树的谱半径[J]. 运筹学学报, 2011, 15(3): 45-50.