可迹图的一些新充分条件

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

Abstract

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

CLC Number:

O157.5

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

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2024.01.011

https://www.ort.shu.edu.cn/EN/Y2024/V28/I1/131

Figures/Tables 6

References 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 $

Some new sufficient condition on traceable graphs

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 10

Related Articles 15

Recommended Articles

Metrics

Comments

$G $	$q(G) $	$\frac{2}{n-1}+2n-6 $	$G $	$q(G) $	$\frac{2}{n-1}+2n-6 $
$K_2\vee(3K_1+K_3) $	$10.172\, 3 $	$10.285\, 7 $	$K_1\vee G_{22} $	$9.690\, 1 $	$10.285\, 7 $
$K_3\vee(4K_1+K_2) $	$12.150\, 5 $	$12.250\, 0 $	$G_{23} $	$9.410\, 6 $	$10.285\, 7 $
$K_2\vee K_{2, 6} $	$13.640\, 2 $	$14.222\, 2 $	$G_{26} $	$9.067\, 1 $	$10.285\, 7 $
$K_2\vee G_{13} $	$13.732\, 4 $	$14.222\, 2 $	$K_2\vee(K_{1, 4}+K_{1}) $	$10.492\, 1 $	$10.285\, 7 $
$K_3\vee(K_1+K_{1, 5}) $	$14.000\, 0 $	$14.222\, 2 $	$K_1\vee K_{2, 5} $	$10.000\, 0 $	$10.285\, 7 $
$K_4\vee6K_1 $	$14.324\, 6 $	$14.222\, 0 $	$K_{3}\vee 5K_1 $	$10.899\, 0 $	$10.285\, 7 $
$2K_1\vee(K_2+3K_1) $	$\ 7.328\, 0 $	$8.333\, 3 $	$G_6 $	$6.156\, 3 $	$6.400\, 0 $
$K_1\vee G_3 $	$\ 7.914\, 2 $	$8.333\, 3 $	$K_1\vee(2K_1+K_{1, 2}) $	$6.494\, 0 $	$6.400\, 0 $
$K_1\vee G_2 $	$\ 7.861\, 3 $	$8.333\, 3 $	$K_1\vee(2K_2+K_1) $	$6.372\, 3 $	$6.400\, 0 $
$K_2\vee 5K_1 $	$\ 8.531\, 1 $	$8.333\, 3 $	$G_8 $	$5.514\, 1 $	$6.400\, 0 $
$K_1\vee(K_1+K_1\vee(K_2+2K_1)) $	$\ 4.599\, 1 $	$8.333\, 3 $	$K_{1}\vee(K_{1, 3}+K_{1}) $	$7.117\, 2 $	$6.400\, 0 $
$K_2\vee(3K_1+K_2) $	$\ 8.735\, 5 $	$8.333\, 3 $	$K_{2, 4} $	$6.000\, 0 $	$6.400\, 0 $
$K_1\vee(K_2\vee4K_{1}+K_{1}) $	$10.118\, 2 $	$10.285\, 7 $	$K_1\vee(K_2+K_{1, 2}) $	$6.626\, 2 $	$6.400\, 0 $
$K_2\vee(2K_1+K_{1, 3}) $	$10.172\, 3 $	$10.285\, 7 $	$K_2\vee4K_1 $	$7.464\, 1 $	$6.400\, 0 $
$K_1\vee G_{19} $	$10.026\, 7 $	$10.285\, 7 $	$G_{37} $	$4.170\, 1 $	$4.500\, 0 $

[1]	Xue JI, Liying KANG, Yisai XUE. The extremal problem of spanning linear forests [J]. Operations Research Transactions, 2025, 29(4): 94-102.
[2]	Yuan WANG, Zhongxun ZHU, Liansheng TAN, Yu YANG. On the upper bound of spectral radius of a class of nonnegative general-tensors and its applications [J]. Operations Research Transactions, 2025, 29(4): 205-218.
[3]	Guidong YU, Hui YUAN, Xinyu XIE. The second largest signless Laplacian spectral radius of uniform supertree with diameter [J]. Operations Research Transactions, 2025, 29(4): 241-248.
[4]	Jiaao LI, Bo SU. Nowhere-zero 5-flows for graphs with bounded genus [J]. Operations Research Transactions, 2025, 29(3): 124-134.
[5]	Zhiwei WU, Liying KANG. The extremal p-spectral radius of cancellative hypergraphs [J]. Operations Research Transactions, 2025, 29(2): 194-200.
[6]	Yu YANG, Zhongxun ZHU, Junpeng ZHOU. The extremal k-uniform hypergraphs with given number of pendent vertices on signless Laplacian spectral radius [J]. Operations Research Transactions, 2025, 29(1): 185-197.
[7]	Linming QI, Weiliang ZHAO, Lianying MIAO. The lower limit of the independence number in edge chromatic critical graphs [J]. Operations Research Transactions, 2025, 29(1): 225-231.
[8]	Xianya GENG, Hui CHAI. Gallai's conjecture for complete bipartite graphs [J]. Operations Research Transactions, 2025, 29(1): 232-238.
[9]	Xuezheng LYU, Mengyu MA. The distance spectra of chain graphs [J]. Operations Research Transactions, 2024, 28(1): 112-120.
[10]	Changxiang HE, Wenyan WANG, Lele LIU. On the eigenvalues and eigenvectors of A_α in weighted non-regular graphs [J]. Operations Research Transactions, 2024, 28(1): 121-130.
[11]	Lele LIU, Bo NING. Unsolved problems in spectral graph theory [J]. Operations Research Transactions, 2023, 27(4): 33-60.
[12]	Huicai JIA, Hongye SONG. Sufficient conditions on Wiener index and Harary index for pancyclic graphs [J]. Operations Research Transactions, 2023, 27(3): 169-177.
[13]	Jie ZHANG, Yan JI. Extremal problems for Steiner Wiener index of unicyclic graphs [J]. Operations Research Transactions, 2023, 27(3): 178-184.
[14]	Yao LIU. On (1, 0)-relaxed strong edge-coloring of graphs [J]. Operations Research Transactions, 2021, 25(2): 115-126.
[15]	Yanxia DONG, Tao XUE, Guang ZHANG. k-tuple domination in generalized de Bruijn digraphs [J]. Operations Research Transactions, 2021, 25(2): 127-134.