Premium
On stability of the hamiltonian index under contractions and closures
Author(s) -
Xiong Liming,
Ryjáček Zdeněk,
Broersma Hajo
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20068
Subject(s) - mathematics , combinatorics , quartic graph , factor critical graph , discrete mathematics , line graph , contractible space , hamiltonian path , graph , graph power
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. © 2005 Wiley Periodicals, Inc. J Graph Theory