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 language | English |
|---|---|
| Pages (from-to) | 104-115 |
| Number of pages | 12 |
| Journal | Journal of Graph Theory |
| Volume | 49 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver