2－阶邻域连通无爪图的Hamilton性  

HAMILTONICITY ON 2-ORDER NEIGHBOR CONNECTED CLAW-FREE GRAPHS

作　　者：李国君[1] 刘振宏[1] 

机构地区：[1]烟台师范学院数学系,中国科学院系统科学研究所

出　　处：《系统科学与数学》1996年第4期335-337,共3页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金;山东省自然科学基金

摘　　要：设Ｇ是无爪图．对ｘ∈Ｖ（Ｇ），若Ｇ［Ｎ（ｘ）］不连通，则存在ｙｉ∈Ｖ（Ｇ）－｛ｘ｝（ｉ－１，２），使｜Ｎ（ｙｉ）∩Ｋｉ（ｘ）｜≥２，且｜Ｎ（ｙｉ）∩Ｎ（Ｋｉ＋１（ｘ））｛ｘ｝｜≥２（ｉ模２），那么称无爪图Ｇ是强２－阶邻域连通的，其中Ｋ１（ｘ），Ｋ２（ｘ）分别表示Ｇ［Ｎ（ｘ）］的两个分支．本文证明了：连通且强２－阶邻域连通的无爪图是Ｈａｍｉｌｔｏｎ图．Let G be a claw-free graph. Forx×∈V(G), as long as G[N(x)] is not connected,there ealst yi∈ V(G) -- {x} (i=1, 2) such that |N(yi)∩ Ki(x)|≥2 andThen the graph G is said to be strongly 2-order neighbor connected, where K1(x) and K2(x) denote, respectively, the two components of G[N(x)].It is proved in this paper that any connected and strongly 2-order neighbor connected claw-free graph is Hamiltonian.

关 键 词：无爪图 邻域连通 最长圈 哈密顿性 连通图 

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