Abstract
In this article, we first show that every 3-edge-connected graph with circumference at most 8 is supereulerian, which is then applied to show that a 3-connected claw-free graph without Z8 as an induced subgraph is Hamiltonian, where Z8 denotes the graph derived from identifying one end vertex of P9 (a path with 9 vertices) with one vertex of a triangle. The above two results are both best possible in a sense that the number 8 cannot be replaced by 9 and they also extend former results by Brousek et al. in (Discrete Math 196 (1999), 29-50) and by Luczak and Pfender in (J Graph Theory 47 (2004), 111-121).
| Original language | English |
|---|---|
| Pages (from-to) | 1-11 |
| Number of pages | 11 |
| Journal | Journal of Graph Theory |
| Volume | 64 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - May 2010 |
Keywords
- Claw-free graphs
- Forbidden subgraphs
- Hamiltonian graphs
- Supereulerian graphs
Fingerprint
Dive into the research topics of 'Every 3-connected Claw-free Z8-Free graph is hamiltonian'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver