Skip to main navigation Skip to search Skip to main content

On stability of the hamiltonian index under contractions and closures

  • Liming Xiong*
  • , Ryjáček Zdeněk
  • , Hajo Broersma
  • *Corresponding author for this work
  • Jiangxi Normal University
  • University of West Bohemia
  • Charles University
  • Durham University

Research output: Contribution to journalArticlepeer-review

Abstract

The hamiltonian index of a graph G is the smallest integer k such that the k-th iterated line graph of G is hamiltonian. We first show that, with one exceptional case, adding an edge to a graph cannot increase its hamiltonian index. We use this result to prove that neither the contraction of an A G(F)-contractible subgraph F of a graph G nor the closure operation performed on G (if G is claw-free) affects the value of the hamiltonian index of a graph G. AMS Subject Classification (2000): 05C45, 05C35.

Original languageEnglish
Pages (from-to)104-115
Number of pages12
JournalJournal of Graph Theory
Volume49
Issue number2
DOIs
Publication statusPublished - Jun 2005

Keywords

  • Closure of a graph
  • Collapsible graph
  • Contractible graph
  • Hamiltonian index
  • Stable property

Fingerprint

Dive into the research topics of 'On stability of the hamiltonian index under contractions and closures'. Together they form a unique fingerprint.

Cite this