摘要
Let G be a graph. Then the hamiltonian index h (G) of G is the smallest number of iterations of line graph operator that yield a hamiltonian graph. In this paper we show that h (G) ≤ max {1, frac(| V (G) | - Δ (G), 3)} for every 2-connected simple graph G that is not isomorphic to the graph obtained from a dipole with three parallel edges by replacing every edge by a path of length l ≥ 3. We also show that max {h (G), h (over(G, -))} ≤ frac(| V (G) | - 3, 6) for any two 2-connected nonhamiltonian graphs G and over(G, -) with at least 74 vertices. The upper bounds are all sharp.
| 源语言 | 英语 |
|---|---|
| 页(从-至) | 6373-6382 |
| 页数 | 10 |
| 期刊 | Discrete Mathematics |
| 卷 | 308 |
| 期 | 24 |
| DOI | |
| 出版状态 | 已出版 - 28 12月 2008 |
学术指纹
探究 'The hamiltonian index of a 2-connected graph' 的科研主题。它们共同构成独一无二的学术指纹。引用此
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver