Abstract
Thomassen conjectured that every 4-connected line graph is Hamiltonian. Lai et al. conjectured [H. Lai, Y. Shao, H. Wu, J. Zhou, Every 3-connected, essentially 11-connected line graph is Hamiltonian, J. Combin. Theory Ser. B 96 (2006) 571-576] that every 3-connected, essentially 4-connected line graph is Hamiltonian. In this note, we first show that the conjecture posed by Lai et al. is not true and there is an infinite family of counterexamples; we show that 3-connected, essentially 4-connected line graph of a graph with at most 9 vertices of degree 3 is Hamiltonian; examples show that all conditions are sharp.
| Original language | English |
|---|---|
| Pages (from-to) | 1835-1838 |
| Number of pages | 4 |
| Journal | Applied Mathematics Letters |
| Volume | 25 |
| Issue number | 11 |
| DOIs | |
| Publication status | Published - Nov 2012 |
Keywords
- Collapsible graph Hamiltonian graph
- Dominating
- Eulerian subgraph
- Line graph
- Super-Eulerian graphs
- Thomassen's conjecture
Fingerprint
Dive into the research topics of 'Hamiltonicity of 3-connected line graphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver