The hamiltonian index of a 2-connected graph

Liming Xiong*, Qiuxin Wu

*此作品的通讯作者

科研成果: 期刊稿件文章同行评审

6 引用 (Scopus)

摘要

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' 的科研主题。它们共同构成独一无二的指纹。

引用此