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