On stability of the hamiltonian index under contractions and closures |
| |
Authors: | Liming Xiong Zdenk Ryj
ek Hajo Broersma |
| |
Institution: | Liming Xiong,Zdeněk Ryjáček,Hajo Broersma |
| |
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 AG(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 |
| |
Keywords: | hamiltonian index stable property closure of a graph contractible graph collapsible graph |
|
|