牛兆宏，乔娟娟

（山西大学 数学科学学院，山西 太原 030006）

0 引言

本文考虑的图均为有限无向无环的图，允许有重边。 空图是指没有任何边的图。 文中未定义的术语和符号参见文献［1］。

图G的线图，记为L(G)，是指以G的边集为顶点集，且两个顶点邻接当且仅当它们在G中（作为边）是邻接的。 设T是图G中的一条迹，当T的起点和终点重合时，称T是闭迹。 若G的每条边至少关联T的一个顶点时，称T是控制的。 Harary 和Nash⁃Williams 在文献［2］中给出了线图L(G)是哈密尔顿的，原图G的一个特征刻画。

定 理1［2］设 图G是 一 个 边 数 大 于 等 于3 的 连通图。 线图L(G)是哈密尔顿的当且仅当G有一条控制闭迹。

对于整数n≥1，图G的n次迭代线图Ln(G)递归地定义为L(Ln-1(G))，其中L0(G)=G且L1(G)=L(G)。 Chartrand 在 文 献［3］中 研 究 了Ln(G)的哈密尔顿性，并引入了哈密尔顿指数，记作h(G)，是使得Ln(G)是哈密尔顿的最小整数n。他证明了对于除去路之外的所有的图，哈密尔顿指数总是存在的。 此后，人们对于图的哈密尔顿指数进行了大量的研究。 Chartrand 和Wall 在文献［4］中研究了树（除路外）的哈密尔顿指数。Ryjáček 等在文献［5］中证明了确定一个图的哈密尔顿指数小于或等于一个给定常数的问题是NP-完全的。 在文献［6］和［7］中，Misra 等和Philip 等分别研究了哈密尔顿指数的算法，并且讨论了算法的时间复杂度。 刘霞和熊黎明在文献［8］中研究了哈密尔顿指数h(G)≤k时的禁用子图集。 其他关于哈密尔顿指数的相关结果，参见综述文献［9］。

记Vi(G)={v∈V(G)：dG(v)=i} 和W(G)=V(G)V2(G)。G的枝是一条非平凡的路，它的端点在W(G) 中且内部顶点（如果有的话）在V2(G)中。 用B(G)表示G中所有的枝构成的集合，并且记