On stability of the hamiltonian index under contractions and closures

Liming Xiong*, Ryjáček Zdeněk, Hajo Broersma

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

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