Hamiltonian iterated line graphs

Liming Xiong; Zhanhong Liu

doi:10.1016/S0012-365X(01)00442-3

Hamiltonian iterated line graphs

Liming Xiong^*, Zhanhong Liu

^*此作品的通讯作者

Jiangxi Normal University

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

31 引用（Scopus）

摘要

The n-iterated line graph of a graph G is Lⁿ(G) = L(L^n-1G)), where L¹G) denotes the line graph L(G) of G, and L^n-1(G) is assumed to be nonempty. Harary and Nash-Williams characterized those graphs G for which L(G) is hamiltonian. In this paper, we will give a characterization of those graphs G for which Lⁿ(G) is hamiltonian, for each n ≥ 2. This is not a simple consequence of Harary and Nash-Williams' result. As an application, we show two methods for determining the hamiltonian index of a graph and enhance various results on the hamiltonian index known earlier.

源语言	英语
页（从-至）	407-422
页数	16
期刊	Discrete Mathematics
卷	256
期	1-2
DOI	https://doi.org/10.1016/S0012-365X(01)00442-3
出版状态	已出版 - 28 9月 2002
已对外发布	是

访问文件

10.1016/S0012-365X(01)00442-3

其它文件与链接

链接到 Scopus 的出版物

引用此

Xiong, L., & Liu, Z. (2002). Hamiltonian iterated line graphs. Discrete Mathematics, 256(1-2), 407-422. https://doi.org/10.1016/S0012-365X(01)00442-3

@article{9d68cdc6bf6a4ab2ab364d123972c2fb,

title = "Hamiltonian iterated line graphs",

abstract = "The n-iterated line graph of a graph G is Ln(G) = L(Ln-1G)), where L1G) denotes the line graph L(G) of G, and Ln-1(G) is assumed to be nonempty. Harary and Nash-Williams characterized those graphs G for which L(G) is hamiltonian. In this paper, we will give a characterization of those graphs G for which Ln(G) is hamiltonian, for each n ≥ 2. This is not a simple consequence of Harary and Nash-Williams' result. As an application, we show two methods for determining the hamiltonian index of a graph and enhance various results on the hamiltonian index known earlier.",

keywords = "Complexity, Contraction of graphs, Hamiltonian index, Iterated line graph, Split block",

author = "Liming Xiong and Zhanhong Liu",

year = "2002",

month = sep,

day = "28",

doi = "10.1016/S0012-365X(01)00442-3",

language = "English",

volume = "256",

pages = "407--422",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

T1 - Hamiltonian iterated line graphs

AU - Xiong, Liming

AU - Liu, Zhanhong

PY - 2002/9/28

Y1 - 2002/9/28

N2 - The n-iterated line graph of a graph G is Ln(G) = L(Ln-1G)), where L1G) denotes the line graph L(G) of G, and Ln-1(G) is assumed to be nonempty. Harary and Nash-Williams characterized those graphs G for which L(G) is hamiltonian. In this paper, we will give a characterization of those graphs G for which Ln(G) is hamiltonian, for each n ≥ 2. This is not a simple consequence of Harary and Nash-Williams' result. As an application, we show two methods for determining the hamiltonian index of a graph and enhance various results on the hamiltonian index known earlier.

AB - The n-iterated line graph of a graph G is Ln(G) = L(Ln-1G)), where L1G) denotes the line graph L(G) of G, and Ln-1(G) is assumed to be nonempty. Harary and Nash-Williams characterized those graphs G for which L(G) is hamiltonian. In this paper, we will give a characterization of those graphs G for which Ln(G) is hamiltonian, for each n ≥ 2. This is not a simple consequence of Harary and Nash-Williams' result. As an application, we show two methods for determining the hamiltonian index of a graph and enhance various results on the hamiltonian index known earlier.

KW - Complexity

KW - Contraction of graphs

KW - Hamiltonian index

KW - Iterated line graph

KW - Split block

UR - http://www.scopus.com/inward/record.url?scp=31244432650&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(01)00442-3

DO - 10.1016/S0012-365X(01)00442-3

M3 - Article

AN - SCOPUS:31244432650

SN - 0012-365X

VL - 256

SP - 407

EP - 422

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-2

ER -

Hamiltonian iterated line graphs

摘要

访问文件

其它文件与链接

指纹

引用此