Degree sum conditions for hamiltonian index

被引：1

作者：

Liu Ze-meng ^{[1
]}

Xiong Li-ming ^{[2
]}

机构：

[1] Beijing Inst Technol, Sch Math & Stat, Beijing 100081, Peoples R China

[2] Beijing Inst Technol, Sch Math & Stat, Beijing Key Lab MCAACI, Beijing 100081, Peoples R China

来源：

APPLIED MATHEMATICS-A JOURNAL OF CHINESE UNIVERSITIES SERIES B | 2021年 / 36卷 / 03期

基金：

中国国家自然科学基金;

关键词：

iterated line graph; hamiltonian index; degree sum condition; CIRCUITS;

D O I：

10.1007/s11766-021-3885-4

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this note, we show a sharp lower bound of min{Sigma(k)(i=1) d(G) (u(i)) : u(1)u(2) ... u(k) is a path of (2-)connected Gg on its order such that (k-1)-iterated line graphs Lk-1 (G) are hamiltonian.

引用

页码：403 / 411

页数：9

共 15 条

[1] ON CIRCUITS AND PANCYCLIC LINE GRAPHS
BENHOCINE, A
CLARK, L
KOHLER, N
VELDMAN, HJ
[J]. JOURNAL OF GRAPH THEORY, 1986, 10 (03) : 411 - 425
[2] Bondy J. A., 2008, GRAPH THEORY, DOI [10.1007/978-1-84628-970-5, DOI 10.1007/978-1-84628-970-5]
[3] HAMILTONIAN LINE GRAPHS
BRUALDI, RA
SHANNY, RF
[J]. JOURNAL OF GRAPH THEORY, 1981, 5 (03) : 307 - 314
[4] HAMILTON CYCLES AND CLOSED TRAILS IN ITERATED LINE GRAPHS
CATLIN, PA
IQBALUNNISA
JANAKIRAMAN, TN
SRINIVASAN, N
[J]. JOURNAL OF GRAPH THEORY, 1990, 14 (03) : 347 - 364
[5] ON HAMILTONIAN LINE-GRAPHS
CHARTRAND, G
[J]. TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1968, 134 (03) : 559 - +
[6] ON HAMILTONIAN LINE GRAPHS
CLARK, L
[J]. JOURNAL OF GRAPH THEORY, 1984, 8 (02) : 303 - 307
[7] Dirac G.A., 1952, Proc. Lond. Math. Soc., V2, P69, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]
[8] Hamiltonian index is NP-complete
Ryjacek, Zdenek
Woeginger, Gerhard J.
Xiong, Liming
[J]. DISCRETE APPLIED MATHEMATICS, 2011, 159 (04) : 246 - 250
[9] A SIMPLE UPPER BOUND FOR THE HAMILTONIAN INDEX OF A GRAPH
SARAZIN, ML
[J]. DISCRETE MATHEMATICS, 1994, 134 (1-3) : 85 - 91
[10] ON DOMINATING AND SPANNING CIRCUITS IN GRAPHS
VELDMAN, HJ
[J]. DISCRETE MATHEMATICS, 1994, 124 (1-3) : 229 - 239

← 1 2 →