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

84 Downloads (Pure)


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
ISSN (Print)0169-2690


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

Cite this