The Hamiltonian index of a graph and its branch-bonds

L. Xiong, X. Liming, Haitze J. Broersma, X. Li, Xueliang Li

Research output: Book/ReportReportProfessional

39 Downloads (Pure)

Abstract

Let $G$ be an undirected and loopless finite graph that is not a path. The minimum $m$ such that the iterated line graph $L^m(G)$ is hamiltonian is called the hamiltonian index of $G,$ denoted by $h(G).$ A reduction method to determine the hamiltonian index of a graph $G$ with $h(G)\geq 2$ is given here. With it we will establish a sharp lower bound and a sharp upper bound for $h(G)$, respectively, which improves some known results of P.A. Catlin et al. [J. Graph Theory 14 (1990)] and H.-J. Lai [Discrete Mathematics 69 (1988)]. Examples show that $h(G)$ may reach all integers between the lower bound and the upper bound.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages13
Publication statusPublished - 2001

Publication series

NameMemorandum Faculteit TW
PublisherUniversity of Twente
No.1611
ISSN (Print)0169-2690

Keywords

  • MSC-05C35
  • EWI-3431
  • MSC-05C45
  • METIS-203117
  • IR-65798

Cite this

Xiong, L., Liming, X., Broersma, H. J., Li, X., & Li, X. (2001). The Hamiltonian index of a graph and its branch-bonds. (Memorandum Faculteit TW; No. 1611). Enschede: University of Twente.
Xiong, L. ; Liming, X. ; Broersma, Haitze J. ; Li, X. ; Li, Xueliang. / The Hamiltonian index of a graph and its branch-bonds. Enschede : University of Twente, 2001. 13 p. (Memorandum Faculteit TW; 1611).
@book{d8f529b742334c4c89c45fdaa852ae6b,
title = "The Hamiltonian index of a graph and its branch-bonds",
abstract = "Let $G$ be an undirected and loopless finite graph that is not a path. The minimum $m$ such that the iterated line graph $L^m(G)$ is hamiltonian is called the hamiltonian index of $G,$ denoted by $h(G).$ A reduction method to determine the hamiltonian index of a graph $G$ with $h(G)\geq 2$ is given here. With it we will establish a sharp lower bound and a sharp upper bound for $h(G)$, respectively, which improves some known results of P.A. Catlin et al. [J. Graph Theory 14 (1990)] and H.-J. Lai [Discrete Mathematics 69 (1988)]. Examples show that $h(G)$ may reach all integers between the lower bound and the upper bound.",
keywords = "MSC-05C35, EWI-3431, MSC-05C45, METIS-203117, IR-65798",
author = "L. Xiong and X. Liming and Broersma, {Haitze J.} and X. Li and Xueliang Li",
note = "Imported from MEMORANDA",
year = "2001",
language = "Undefined",
series = "Memorandum Faculteit TW",
publisher = "University of Twente",
number = "1611",
address = "Netherlands",

}

Xiong, L, Liming, X, Broersma, HJ, Li, X & Li, X 2001, The Hamiltonian index of a graph and its branch-bonds. Memorandum Faculteit TW, no. 1611, University of Twente, Enschede.

The Hamiltonian index of a graph and its branch-bonds. / Xiong, L.; Liming, X.; Broersma, Haitze J.; Li, X.; Li, Xueliang.

Enschede : University of Twente, 2001. 13 p. (Memorandum Faculteit TW; No. 1611).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - The Hamiltonian index of a graph and its branch-bonds

AU - Xiong, L.

AU - Liming, X.

AU - Broersma, Haitze J.

AU - Li, X.

AU - Li, Xueliang

N1 - Imported from MEMORANDA

PY - 2001

Y1 - 2001

N2 - Let $G$ be an undirected and loopless finite graph that is not a path. The minimum $m$ such that the iterated line graph $L^m(G)$ is hamiltonian is called the hamiltonian index of $G,$ denoted by $h(G).$ A reduction method to determine the hamiltonian index of a graph $G$ with $h(G)\geq 2$ is given here. With it we will establish a sharp lower bound and a sharp upper bound for $h(G)$, respectively, which improves some known results of P.A. Catlin et al. [J. Graph Theory 14 (1990)] and H.-J. Lai [Discrete Mathematics 69 (1988)]. Examples show that $h(G)$ may reach all integers between the lower bound and the upper bound.

AB - Let $G$ be an undirected and loopless finite graph that is not a path. The minimum $m$ such that the iterated line graph $L^m(G)$ is hamiltonian is called the hamiltonian index of $G,$ denoted by $h(G).$ A reduction method to determine the hamiltonian index of a graph $G$ with $h(G)\geq 2$ is given here. With it we will establish a sharp lower bound and a sharp upper bound for $h(G)$, respectively, which improves some known results of P.A. Catlin et al. [J. Graph Theory 14 (1990)] and H.-J. Lai [Discrete Mathematics 69 (1988)]. Examples show that $h(G)$ may reach all integers between the lower bound and the upper bound.

KW - MSC-05C35

KW - EWI-3431

KW - MSC-05C45

KW - METIS-203117

KW - IR-65798

M3 - Report

T3 - Memorandum Faculteit TW

BT - The Hamiltonian index of a graph and its branch-bonds

PB - University of Twente

CY - Enschede

ER -

Xiong L, Liming X, Broersma HJ, Li X, Li X. The Hamiltonian index of a graph and its branch-bonds. Enschede: University of Twente, 2001. 13 p. (Memorandum Faculteit TW; 1611).