图的线图是Hamiltonian的一个充分条件

A Sufficient Condition for the Line Graph L(G) of a Graph Is a Hamiltonian

证明顶点数n≥3的几乎无桥连通图G,GK1,n-1,若对G中任意互不相邻的3条边e1,e2,e3满足dG(e1)+dG(e2)+dG(e3)≥2n+1,则G有一条D迹,从而其线图L(G)是Hamiltonian.

It is proved that if G be a connected almost bridgeless graph on n vertices (n≥3),with GK 1,n-1 .Suppose d G(e 1)+d G(e 2)+d G(e 3)≥2n+1 for every set of three independent edges of E(G),then G contains a D circuit,such that L(G) is a hamiltonian.