Neighborhood Intersections and Hamiltonian property in Claw-Free Graphs

ＮｅｉｇｈｂｏｒｈｏｏｄＩｎｔｅｒｓｅｃｔｉｏｎｓａｎｄＨａｍｉｌｔｏｎｉａｎｐｒｏｐｅｒｔｙｉｎＣｌａｗＦｒｅｅＧｒａｐｈｓＷａｎｇＤｏｎｇｄｏｎｇ（王冬冬）（ＨｕａｉｙｉｎＩｎｄｕｓｔｒｙＣｏｌｅｇｅ，Ｈｕａｉｙｉｎｇ２２３０００）Ａｂｓ...

LONGEST CYCLES IN 2-CONNECTEDCLAW-FREE GRAPHS

M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + 2, n} or G belongs to one exceptional class of graphs.

无K_(1,r)图中的哈密顿圈(英文)

本文借助于对图的本质独立集和图的部分平方图的独立集的研究,对无K1,r图中哈密顿圈的存在性给出了八个充分条件.我们将利用T-插点技术对这八个充分条件给出统一的证明.本文的结果从本质上改进了C-Q.Zhang于1988年利用次形条件给出的k-连通无爪图是哈密顿图的次型充分条件;同时,G.Chen和R.H.Schelp在1995年利用次型条件给出的关于k-连通无K1、4图是哈密顿图的充分条件也被我们的结果改进并推广到无K1,r图.

无爪图中的邻集交和Hamilton性质

本文证明了如下结果：设 Ｃ是ｎ阶２连通无爪图，Ｋ为连通度，若对 Ｃ中每一个阶为Ｋ＋ １的独立集 Ｓ，存在ｕ，ｖ∈ Ｓ，有 １Ｎ（ｕ） １≥（ｎ－ ２ｋ）１４，则 Ｃ是Ｈａｍｉｌｔｏｎ图。

3-连通无爪图中的最长圈

证明了3-连通无爪图G中的最长圈C满足:|V(C)|≥min{3δ(G)+6,5δ(G)-5,4δ(G),|V(G)|}.

3－连通正则无爪图的Hamilton圈

本文证明了：任一阶数不超过６ｋ—４的３－连通ｋ－正则无爪图是Ｈａｍｉｌｔｏｎ的．

k-连通无爪图中存在哈密尔顿圈的一个隐度条件

文中给出了强基本独立集的概念,并证明了如下定理:设G是一个具有n个顶点的k-连通无爪图,其中k≥2.如果对任意一个具有k个顶点的强基本独立集S,都有max{d2(x)|x∈S}≥n 2,则G是哈密尔顿图.此定理在无爪图的条件下推广了已有的几个有关图中哈密尔顿圈存在性的定理.

4连通无爪图的最长圈

设Ｇ为ｎ阶４连通无爪图，δ＝ｍｉｎ｛ｄ（ｘ）｜ｘ∈Ｖ（Ｇ）｝，则当ｎ≤６δ－１１时Ｇ为Ｈ图；

5连通无爪图的最长圈

设Ｇ为ｎ阶５连通无爪图，σ６＝ｍｉｎ｛∑ｘ∈Ｉ６ｄ（ｘ）｜Ｉ６为Ｇ的６点独立集｝，则Ｃ（Ｇ）≥ｍｉｎ｛ｎ，σ６－１１｝。

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

设Ｇ是无爪图．对ｘ∈Ｖ（Ｇ），若Ｇ［Ｎ（ｘ）］不连通，则存在ｙｉ∈Ｖ（Ｇ）－｛ｘ｝（ｉ－１，２），使｜Ｎ（ｙｉ）∩Ｋｉ（ｘ）｜≥２，且｜Ｎ（ｙｉ）∩Ｎ（Ｋｉ＋１（ｘ））｛ｘ｝｜≥２（ｉ模２），那么称无爪图Ｇ是强２－阶邻域连通的，其中Ｋ１（ｘ），Ｋ２（ｘ）分别表示Ｇ［Ｎ（ｘ）］的两个分支．本文证明了：连通且强２－阶邻域连通的无爪图是Ｈａｍｉｌｔｏｎ图．