On Traceable Line Graphs

Zhaohong Niu; Liming Xiong

doi:10.1007/s00373-013-1371-3

On Traceable Line Graphs

Zhaohong Niu, Liming Xiong^*

^*Corresponding author for this work

School of Mathematics and Statistics

Research output: Contribution to journal › Article › peer-review

Abstract

Let G be a simple graph of order n and D₁(G) be the set of vertices of degree 1 in G. In this paper, we prove that if G − D₁(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.

Original language	English
Pages (from-to)	221-233
Number of pages	13
Journal	Graphs and Combinatorics
Volume	31
Issue number	1
DOIs	https://doi.org/10.1007/s00373-013-1371-3
Publication status	Published - Jan 2015

Keywords

Dominating trail
F-trail
Hamiltonian cycle (path)
Line graph

Access to Document

10.1007/s00373-013-1371-3

Cite this

Niu, Z., & Xiong, L. (2015). On Traceable Line Graphs. Graphs and Combinatorics, 31(1), 221-233. https://doi.org/10.1007/s00373-013-1371-3

@article{dfd3cbc787b8487eb785e13c66b2cf11,

title = "On Traceable Line Graphs",

abstract = "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.",

keywords = "Dominating trail, F-trail, Hamiltonian cycle (path), Line graph",

author = "Zhaohong Niu and Liming Xiong",

note = "Publisher Copyright: {\textcopyright} 2013, Springer Japan.",

year = "2015",

month = jan,

doi = "10.1007/s00373-013-1371-3",

language = "English",

volume = "31",

pages = "221--233",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "1",

}

TY - JOUR

T1 - On Traceable Line Graphs

AU - Niu, Zhaohong

AU - Xiong, Liming

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 -

On Traceable Line Graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this