The Hamiltonian index of a graph and its branch-bonds

L. Xiong, H.J. Broersma, X. Li

Research output: Book/ReportReportProfessional

92 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 languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages13
Publication statusPublished - 2001

Publication series

NameMemorandum
PublisherUniversity of Twente, Faculty of Mathematical Sciences
No.1611
ISSN (Print)0169-2690

Keywords

  • MSC-05C35
  • MSC-05C45

Fingerprint

Dive into the research topics of 'The Hamiltonian index of a graph and its branch-bonds'. Together they form a unique fingerprint.

Cite this