图中含有D-闭迹的一个充分条件  

A NEW SUFFICIENT CONDITION FORHAMILTONIAN LINE GRAPHS

作　　者：刘春峰 

机构地区：[1]锦州师范高等专科学校

出　　处：《纯粹数学与应用数学》1998年第1期42-46,共5页Pure and Applied Mathematics

摘　　要：设Ｇ是一个简单图，Ｌ＝ｕ１ｕ２…ｕｔ是Ｇ中的一个路，定义Ｌ的度ｄ（Ｌ）＝∑ｔｉ＝１ｄ（ｕｉ），其中ｄ（ｕｉ）为ｕｉ在Ｇ中的度数．本文证明了：若Ｇ是ｎ≥３阶几乎无桥的简单连通图，ＧＫ１，ｎ－１，且对Ｇ中任何两个无公共点的二长路Ｌ１，Ｌ２，有ｄ（Ｌ１）＋ｄ（Ｌ２）≥２ｎ－１，则Ｇ有一个Ｄ－闭迹，从而Ｇ的线图Ｌ（Ｇ）是Ｈａｍｉｌｔｏｎ图．おor a path L=u1u2…ut of simple graph G, let d(L)=∑ti=1d(ui), where d(ui) are degree of the vertices ui. H is a path of length 2.The main result is as follows: Let G be a simple connected, almost bridgeless graph of order n≥3, GK1,n-1. If for each pair of path L1 and L2 which have no common vertex, and 〈Li〉≌H,i=1,2, d(L1)+d(L2)≥2n-1, then the line graph L(G) of G has a Hamiltonian cycle.

关 键 词：D-闭迹 哈密顿图 线图 图论 简单图 

分 类 号：O157.5[理学—数学]