TY - JOUR
T1 - On Traceable Line Graphs
AU - Niu, Zhaohong
AU - Xiong, Liming
N1 - Publisher Copyright:
© 2013, Springer Japan.
PY - 2015/1
Y1 - 2015/1
N2 - Let G be a simple graph of order n and D1(G) be the set of vertices of degree 1 in G. In this paper, we prove that if G − D1(G) is 2-edge-connected and if for every edge (formula presented)(formula presented), max(d(x), d(y)) ≥ n/6−1, then for n large, L(G) is traceable with the exception of a class of well characterized graphs. A similar result in (Lai, Discrete Math 178:93–107, 1998) states that if we replace 6 by 5 in the above degree condition, then for n large, L(G) is Hamiltonian with the exception of a class of well characterized graphs.
AB - Let G be a simple graph of order n and D1(G) be the set of vertices of degree 1 in G. In this paper, we prove that if G − D1(G) is 2-edge-connected and if for every edge (formula presented)(formula presented), max(d(x), d(y)) ≥ n/6−1, then for n large, L(G) is traceable with the exception of a class of well characterized graphs. A similar result in (Lai, Discrete Math 178:93–107, 1998) states that if we replace 6 by 5 in the above degree condition, then for n large, L(G) is Hamiltonian with the exception of a class of well characterized graphs.
KW - Dominating trail
KW - F-trail
KW - Hamiltonian cycle (path)
KW - Line graph
UR - http://www.scopus.com/inward/record.url?scp=84943589183&partnerID=8YFLogxK
U2 - 10.1007/s00373-013-1371-3
DO - 10.1007/s00373-013-1371-3
M3 - Article
AN - SCOPUS:84943589183
SN - 0911-0119
VL - 31
SP - 221
EP - 233
JO - Graphs and Combinatorics
JF - Graphs and Combinatorics
IS - 1
ER -