On Traceable Line Graphs

Zhaohong Niu; Liming Xiong

doi:10.1007/s00373-013-1371-3

On Traceable Line Graphs

Zhaohong Niu, Liming Xiong^*

^*此作品的通讯作者

数学学院

科研成果: 期刊稿件 › 文章 › 同行评审

摘要

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.

源语言	英语
页（从-至）	221-233
页数	13
期刊	Graphs and Combinatorics
卷	31
期	1
DOI	https://doi.org/10.1007/s00373-013-1371-3
出版状态	已出版 - 1月 2015

访问文件

10.1007/s00373-013-1371-3

其它文件与链接

链接到 Scopus 的出版物

引用此

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

摘要

访问文件

其它文件与链接

指纹

引用此