哈密顿线图的一个充分条件

A Sufficient Condition for Hamiltonian Line Graphs

本文得到如下结果:设G是几乎无桥P≥2阶简单连通图,且G(?)K_(1,p-1),若对任意相距为1的两边e_0和e_1,d(e_0)+d(e_1)≥2P-5,则G有一个D一闭迹,从而G的线图L(G)是哈密尔顿的。

For each edge e=uv of a graph G, let d(e)=d(u)+d(v) where d(u) and d(v) are the degrees of the vertices u and v respectively. The main result is as follows: Let G be a simple connected, almost bridgeless graph of order P≥2, G(?) K_(1,p-1).If d(e_1)+d(e_2)≥2p—5 for each pair of edges e_1 and e_2 such that the distance between e_1 and e_2 is 1,then the line graph L(G) of G has Hamiltoni an cycle, i.e.,G is a Hamiltonian line graph.