The Hamiltonian index of graphs

Yi Hong; Jian-Liang Lin; Zhi-Sui Tao; Zhi-Hong Chen

doi:10.1016/j.disc.2007.12.105

The Hamiltonian index of graphs

Yi Hong
, Jian-Liang Lin
, Zhi-Sui Tao
, Zhi-Hong Chen

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

Abstract

The Hamiltonian index of a graph G is defined as h ( G ) = min { m : L m ( G ) is Hamiltonian } . In this paper, using the reduction method of Catlin [P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44], we constructed a graph H ̃ ( m ) ( G ) from G and prove that if h ( G ) ≥ 2 , then h ( G ) = min{ m : H ̃ ( m ) ( G ) has a spanning Eulerian subgraph }.

Original language	American English
Journal	Scholarship and Professional Work - LAS
Volume	309
Issue number	1
DOIs	https://doi.org/10.1016/j.disc.2007.12.105
State	Published - Jan 1 2009

Keywords

Collapsible graph
Hamiltonian index
Line graph

Disciplines

Computer Sciences
Mathematics

Access to Document

10.1016/j.disc.2007.12.105License: Unspecified

The Hamiltonian index of graphsFinal published version, 1.07 MBLicense: Unspecified

Cite this

@article{1673fa3d9c424b209722abed78665040,

title = "The Hamiltonian index of graphs",

abstract = " The Hamiltonian index of a graph G is defined as h ( G ) = min \{ m : L m ( G ) is Hamiltonian \} . In this paper, using the reduction method of Catlin [P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44], we constructed a graph H{\~ } ( m ) ( G ) from G and prove that if h ( G ) ≥ 2 , then h ( G ) = min\{ m : H{\~ } ( m ) ( G ) has a spanning Eulerian subgraph \}.",

keywords = "Collapsible graph, Hamiltonian index, Line graph",

author = "Yi Hong and Jian-Liang Lin and Zhi-Sui Tao and Zhi-Hong Chen",

year = "2009",

month = jan,

day = "1",

doi = "10.1016/j.disc.2007.12.105",

language = "American English",

volume = "309",

journal = "Scholarship and Professional Work - LAS",

number = "1",

}

TY - JOUR

T1 - The Hamiltonian index of graphs

AU - Hong, Yi

AU - Lin, Jian-Liang

AU - Tao, Zhi-Sui

AU - Chen, Zhi-Hong

PY - 2009/1/1

Y1 - 2009/1/1

N2 - The Hamiltonian index of a graph G is defined as h ( G ) = min { m : L m ( G ) is Hamiltonian } . In this paper, using the reduction method of Catlin [P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44], we constructed a graph H ̃ ( m ) ( G ) from G and prove that if h ( G ) ≥ 2 , then h ( G ) = min{ m : H ̃ ( m ) ( G ) has a spanning Eulerian subgraph }.

AB - The Hamiltonian index of a graph G is defined as h ( G ) = min { m : L m ( G ) is Hamiltonian } . In this paper, using the reduction method of Catlin [P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44], we constructed a graph H ̃ ( m ) ( G ) from G and prove that if h ( G ) ≥ 2 , then h ( G ) = min{ m : H ̃ ( m ) ( G ) has a spanning Eulerian subgraph }.

KW - Collapsible graph

KW - Hamiltonian index

KW - Line graph

UR - https://digitalcommons.butler.edu/facsch_papers/143

U2 - 10.1016/j.disc.2007.12.105

DO - 10.1016/j.disc.2007.12.105

M3 - Article

VL - 309

JO - Scholarship and Professional Work - LAS

JF - Scholarship and Professional Work - LAS

IS - 1

ER -

The Hamiltonian index of graphs

Abstract

Keywords

Disciplines

Access to Document

Other files and links

Cite this