摘要
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 |