A Note on Edge-Disjoint Hamilton Cycles in Line Graphs

被引：8

作者：

Li, Hao ^{[1
,2
]}

He, Weihua ^{[1
,3
]}

Yang, Weihua ^{[4
]}

Bai, Yandong ^{[1
]}

机构：

[1] Univ Paris 11, CNRS, Rech Informat Lab, UMR 8623, F-91405 Orsay, France

[2] Jianghan Univ, Inst Interdisciplinary Res, Wuhan, Peoples R China

[3] Guangdong Univ Technol, Dept Appl Math, Guangzhou, Guangdong, Peoples R China

[4] Taiyuan Univ Technol, Dept Math, Taiyuan, Peoples R China

来源：

GRAPHS AND COMBINATORICS | 2016年 / 32卷 / 02期

关键词：

Hamilton cycle; Edge-disjoint Hamilton cycles; Line graph; CLAW-FREE GRAPHS; CONNECTEDNESS;

D O I：

10.1007/s00373-015-1606-6

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It is well known that if a graph G contains a spanning closed trail, then its line graph L(G) is Hamiltonian. In this note, it is proved that if a graph G with minimum degree at least 4k has k edge-disjoint spanning closed trails, then L(G) contains k edge-disjoint Hamilton cycles.

引用

页码：741 / 744

页数：4

共 14 条

[1] Alspach B., 1990, Cycles and Rays, P9, DOI [10.1007/978-94-009-0517-72, DOI 10.1007/978-94-009-0517-72]
[2] Bondy J., 2008, GRADUATE TEXTS MATH
[3] Harary S. L., 1965, CAN MATH B, V8, P701
[4] NOTE ON SUB-EULERIAN GRAPHS
JAEGER, F
[J]. JOURNAL OF GRAPH THEORY, 1979, 3 (01) : 91 - 93
[5] Kundu S., 1974, J COMB THEORY B, V17, P199
[6] Every 3-connected, essentially 11-connected line graph is Hamiltonian
Lai, HH
Shao, YH
Wu, HH
Zhou, J
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (04) : 571 - 576
[7] EVERY 4-CONNECTED LINE GRAPH OF A PLANAR GRAPH IS HAMILTONIAN
LAI, HJ
[J]. GRAPHS AND COMBINATORICS, 1994, 10 (03) : 249 - 253
[8] Every 4-connected line graph of a quasi claw-free graph is hamiltonian connected
Lai, Hong-Jian
Shao, Yehong
Zhan, Mingquan
[J]. DISCRETE MATHEMATICS, 2008, 308 (22) : 5312 - 5316
[9] Hamiltonian connectedness in 3-connected line graphs
Lai, Hong-Jian
Shao, Yehong
Yu, Gexin
Zhan, Mingquan
[J]. DISCRETE APPLIED MATHEMATICS, 2009, 157 (05) : 982 - 990
[10] Every 3-Connected Claw-Free Z8-Free Graph Is Hamiltonian
Lai, Hong-Jian
Xiong, Liming
Yan, Huiya
Yan, Jin
[J]. JOURNAL OF GRAPH THEORY, 2010, 64 (01) : 1 - 11

← 1 2 →