可迹图的一些新充分条件

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

摘要/Abstract

摘要：

设图$G$是一个简单连通图, $e(G)$、$\mu(G)$和$q(G)$分别为图$G$的边数、谱半径和无符号拉普拉斯谱半径。如果一个图含有一条包含所有顶点的路, 则这条路为哈密尔顿路, 称这个图为可迹图。本文主要研究利用$e(G)$、$\mu(G)$和$q(G)$分别给出图$G$是可迹图的一些新充分条件, 所得结果推广了已有的结论。

关键词: 图, 可迹图, 边数, 谱半径, 无符号拉普拉斯谱半径

Abstract:

Let $G$ be a simple connected graph, $e(G)$, $\mu(G)$ and $q(G)$ be the edge number, the spectral radius and the signless Laplacian spectral radius of the graph $G$, respectively. If a graph has a path which contains all vertices of the graph, the path is called a Hamilton path, the graph is called traceable graph. In this paper, we present some new sufficient conditions for the graph to be traceable graph in terms of $e(G)$, $\mu(G)$ and $q(G)$, respectively. The results generalize the existing conclusions.

Key words: graphs, traceable graph, edge number, spectral radius, signless Laplacian spectral radius

中图分类号:

O157.5

余桂东, 刘珍珍, 王礼想, 李青. 可迹图的一些新充分条件[J]. 运筹学学报, 2024, 28(1): 131-140.

Guidong YU, Zhenzhen LIU, Lixiang WANG, Qing LI. Some new sufficient condition on traceable graphs[J]. Operations Research Transactions, 2024, 28(1): 131-140.

图/表 6

表1

表2

表3

表4

表5

表6

参考文献 10

1	Fiedler M , Nikiforov V . Spectral radius and Hamiltonicity of graphs[J]. Linear Algebra and Its Applications, 2010, 432, 2170- 2173. doi: 10.1016/j.laa.2009.01.005
2	Zhou B . Signless Laplacian spectral radius and Hamiltonicity[J]. Linear Algebra and Its Applications, 2010, 432 (2/3): 566- 570.
3	Lu M , Liu H Q , Tian F . Spectral radius and Hamiltonian graphs[J]. Linear Algebra and Its Applications, 2012, 437 (7): 1670- 1674. doi: 10.1016/j.laa.2012.05.021
4	Yu G D , Fan Y Z . Spectral conditions for a graph to be Hamilton-connected[J]. Applied Mechanics & Materials, 2013, 336-338, 2329- 2334.
5	Liu R F , Shiu W C , Xue J . Sufficient spectral conditions on Hamiltonian[J]. Linear Algebra and Its Applications, 2015, 467, 254- 266. doi: 10.1016/j.laa.2014.11.017
6	Zhou Q N , Wang L G . Some sufficient spectral conditions on Hamilton-connected and traceable graphs[J]. Linear and Multilinear Algebra, 2017, 65, 224- 234. doi: 10.1080/03081087.2016.1182463
7	贾会才, 薛杰. 哈密顿连通图和可迹图的新充分谱条件[J]. 数学的实践与认识, 2017, 47 (11): 272- 276.
8	Ning B , Ge J . Spectral radius and Hamiltonian properties of graphs[J]. Linear and Multilinear Algebra, 2015, 63 (8): 1520- 1530. doi: 10.1080/03081087.2014.947984
9	Bondy J A , Murty U S R . Graph Theory[M]. New York: Springer, 2008.
10	Yuan H . A bound on the spectral radius of graphs[J]. Linear Algebra and Its Applications, 1988, 108, 135- 139. doi: 10.1016/0024-3795(88)90183-8

度和	序号	度序列	图	不可迹图
$58 $	$1 $	$(4^6, 8^2, 9^2) $	$K_2\vee K_{2, 6}, K_2\vee G_{13} $	$K_2\vee K_{2, 6}, K_2\vee G_{13} $
	$2 $	$(3^1, 4^5, 8^1, 9^3) $	$K_3\vee(K_1+K_{1, 5}) $	$K_3\vee(K_1+K_{1, 5}) $
$60 $	$3 $	$(4^6, 9^4) $	$K_4\vee6K_1 $	$K_4\vee6K_1 $

度和	序号	度序列	图	不可迹图
22	1	$(2^3, 3^2, 5^2) $	$2K_1\vee (K_2+3K_1), G_7, G_{11}, G_{12} $	$2K_1\vee (K_2+3K_1) $
	2	$(2^3, 3^2, 4^1, 6^1) $	$K_1\vee G_1, K_1\vee G_3, K_1\vee(K_2+K_1\vee(K_1+K_2)) $	$K_1\vee G_3 $
	3	$(2^4, 3^1, 5^1, 6^1) $	$K_1\vee G_2 $	$K_1\vee G_2 $
	4	$(2^5, 6^2) $	$K_2\vee 5K_1 $	$K_2\vee 5K_1 $
	5	$(1^1, 2^2, 3^2, 5^1, 6^1) $	$K_1\vee (K_1+K_1\vee (K_2+2K_1)) $	$K_1\vee (K_1+K_1\vee (K_2+2K_1)) $
24	$6 $	$(2^3, 3^2, 6^2) $	$K_2\vee(3K_1+K_2) $	$K_2\vee(3K_1+K_2) $

度和	序号	度序列	图	不可迹图
32	1	$(1^1, 3^4, 6^2, 7^1) $	$K_{1}\vee(K_{2}\vee4K_{1}+K_{1}) $	$K_{1}\vee(K_{2}\vee 4K_{1}+K_{1}) $
	2	$(2^2, 3^3, 5^1, 7^2) $	$K_{2}\vee(2K_{1}+K_{1, 3}) $	$K_{2}\vee(2K_{1}+K_{1, 3}) $
	3	$(2^2, 3^3, 6^2, 7^1) $	$K_{1}\vee G_{19} $	$K_{1}\vee G_{19} $
	4	$(2^1, 3^4, 4^1, 7^2) $	$G_{20} $	可迹
	5	$(2^1, 3^4, 5^1, 6^1, 7^1) $	$K_{1}\vee G_{21} $, $K_{1}\vee G_{22} $	$K_{1}\vee G_{22} $
	6	$(2^1, 3^4, 6^3) $	$G_{23} $	$G_{23} $
	7	$(3^6, 7^2) $	$K_{2}\vee3K_{2} $	可迹
	8	$(3^5, 5^2, 7^1) $	$K_{1}\vee G_{24} $, $K_{1}\vee G_{25} $, $K_{1}\vee G_{31} $	可迹
	9	$(3^5, 5^1, 6^2) $	$G_{26} $, $G_{27}, G_{32} $, $G_{33} $	$G_{26} $
	10	$(3^5, 4^1, 6^1, 7^1)$	$K_{1}\vee G_{28}$, $K_{1}\vee G_{29}$, $K_{1}\vee G_{34}$	可迹
34	11	$(2^1, 3^4, 6^1, 7^2)$	$K_2\vee(K_{1, 4}+K_{1})$	$K_2\vee(K_{1, 4}+ K_{1})$
	12	$(3^5, 5^1, 7^2)$	$K_2\vee(K_2+K_{1, 3})$	可迹
	13	$(3^5, 6^2, 7^1)$	$K_{1}\vee K_{2, 5}$, $K_{1}\vee G_{30}$	$K_{1}\vee K_{2, 5}$
36	14	$(3^5, 7^3)$	$K_3\vee 5K_1$	$K_3\vee 5K_1$

度和	序号	度序列	图	不可迹图
14	1	$(2^5, 4^1) $	$G_4 $	可迹
	2	$(2^4, 3^2) $	$G_5, G_{16}, G_{17} $	可迹
	3	$(1^2, 2^2, 4^2) $	$G_6 $	$G_6 $
	4	$(1^2, 2^2, 3^1, 5^1) $	$K_1\vee(2K_1+K_{1, 2}) $	$K_1\vee(2K_1+K_{1, 2}) $
	5	$(1^1, 2^4, 5^1) $	$K_1\vee(2K_2+K_1) $	$K_1\vee(2K_2+K_1) $
	6	$(1^1, 2^3, 3^1, 4^1) $	$G_8, G_9, G_{10}, G_{15} $	$G_8 $
16	7	$(1^1, 2^3, 4^1, 5^1) $	$K_1\vee(K_1+K_{1, 3}) $	$K_{1}\vee(K_{1, 3}+K_{1}) $
	8	$(2^4, 4^2) $	$K_{2, 4}, G_{14} $	$K_{2, 4} $
	9	$(2^4, 3^1, 5^1) $	$K_1\vee(K_2+K_{1, 2}) $	$K_1\vee(K_2+K_{1, 2}) $
18	10	$(2^4, 5^2) $	$K_2\vee4K_1 $	$K_2\vee4K_1 $

$G $	$\mu(G) $	$\sqrt{n^2-6n+7} $	$G $	$\mu(G) $	$\sqrt{n^2-6n+7} $
$K_2\vee(3K_1+K_3) $	$4.605\, 6 $	$4.795\, 8 $	$K_1\vee G_{22} $	$4.418\, 2 $	$5.385\, 2 $
$K_3\vee(4K_1+K_2) $	$5.509\, 0 $	$5.831\, 0 $	$G_{23} $	$4.385\, 5 $	$5.385\, 2 $
$K_2\vee K_{2, 6} $	$6.325\, 9 $	$6.855\, 6 $	$G_{26} $	$4.251\, 5 $	$5.385\, 2 $
$K_2\vee G_{13} $	$6.363\, 9 $	$6.855\, 6 $	$K_2\vee(K_{1, 4}+K_{1}) $	$4.790\, 3 $	$5.385\, 2 $
$K_3\vee(K_1+K_{1, 5}) $	$6.453\, 3 $	$6.855\, 6 $	$K_1\vee K_{2, 5} $	$4.618\, 5 $	$5.385\, 2 $
$K_4\vee6K_1 $	$6.623\, 5 $	$6.855\, 6$	$K_{3}\vee 5K_1 $	$5.000\, 0 $	$5.385\, 2 $
$2K_1\vee(K_2+3K_1) $	$3.414\, 2 $	$3.741\, 7 $	$G_6 $	$2.791\, 3 $	$2.645\, 8 $
$K_1\vee G_3 $	$3.520\, 1 $	$3.741\, 7 $	$K_1\vee(2K_1+K_{1, 2}) $	$2.813\, 6 $	$2.645\, 8 $
$K_1\vee G_2 $	$3.446\, 4 $	$3.741\, 7 $	$K_1\vee(2K_2+K_1) $	$2.709\, 3 $	$2.645\, 8 $
$K_2\vee 5K_1 $	$3.701\, 6 $	$3.741\, 7 $	$G_8 $	$2.557\, 6 $	$2.645\, 8 $
$K_1\vee(K_1+K_1\vee(K_2+2K_1)) $	$3.700\, 9 $	$3.741\, 7 $	$K_{1}\vee(K_{1, 3}+K_{1}) $	$3.135\, 3 $	$2.645\, 8 $
$K_2\vee(3K_1+K_2) $	$3.909\, 5 $	$3.741\, 7 $	$K_{2, 4} $	$2.828\, 4 $	$2.645\, 8 $
$K_1\vee(K_2\vee4K_{1}+K_{1}) $	$4.652\, 7 $	$5.385\, 2 $	$K_1\vee(K_2+K_{1, 2}) $	$2.947\, 4 $	$2.645\, 8 $
$K_2\vee(2K_1+K_{1, 3}) $	$4.579\, 6 $	$5.385\, 2 $	$K_2\vee4K_1 $	$3.372\, 3 $	$2.645\, 8 $
$K_1\vee G_{19} $	$4.564\, 0 $	$5.385\, 2 $	$G_{37} $	$1.847\, 7 $	$1.414\, 2 $