Closure and stable Hamiltonian properties in claw‐free graphs |
| |
Authors: | Stephan Brandt,Odile Favaron,Zdeně k Ryjá č ek |
| |
Abstract: | In the class of k‐connected claw‐free graphs, we study the stability of some Hamiltonian properties under a closure operation introduced by the third author. We prove that (i) the properties of pancyclicity, vertex pancyclicity and cycle extendability are not stable for any k (i.e., for any of these properties there is an infinite family of graphs Gk of arbitrarily high connectivity k such that the closure of Gk has the property while the graph Gk does not); (ii) traceability is a stable property even for k = 1; (iii) homogeneous traceability is not stable for k = 2 (although it is stable for k = 7). The article is concluded with several open questions concerning stability of homogeneous traceability and Hamiltonian connectedness. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 30–41, 2000 |
| |
Keywords: | closure claw‐free graphs stable property Hamiltonicity pancyclicity cycle extendability traceability |
|
|