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.

A NOTE ON CONNECTED FACTORS IN CLAW-FREE GRAPHS

In this paper it is shown that every connected claw-free graph G contains connected [a, max{a + 2, b}]-factors if it has [a, b]-factors, where a, b are integers and b ≥ a ≥ 1.

PATH EXTENSIBILITY OF CONNECTED,LOCALLY 2-CONNECTED K_(1,3)-FREE GRAPHS

In this paper, we prove that every connected, locally 2-connected claw-freegraph is path extendable.

Neighborhood Intersections and Hamiltonian property in Claw-Free Graphs

We prove the following result: Let G be a 2 connected claw free graph of order n(n≥3) and connectivity k . If for any independent set S k+1 with cardinality k+1 , there exist u,v∈S k+1 , such that |N(u)∩N(v)|≥(n-2k)/4 ,then G is Hamiltonian.

ON 2-FACTORS IN CLAW-FREE GRAPHS

Ｎｏｗｓｔｕｄｙｉｎｇｆｏｒｄｏｃｔｏｒ＇ｓｄｅｇｒｅｅａｔｉｎｓｔｉｔｕｔｅｏｆＳｙｓｔｅｍｓＳｃｉｅｎｃｅ，ＡｃａｄｅｍｉａＳｉｎｉｃａ．ＴｈｅｏｒｅｍＤＩ４］Ｌｅｔｋ２１ｂｅａｎｉｎｔｅｇｅｒ．ＩｆＧｉｓａｃｏｎｎｅｃｔｅｄｃｌａｗ－ｆｒｅｅｇｍｐｈｗｉｔｈｈｉＶ（Ｇ）ｌｅｖｅｎａｎｄｗｉｔｈｍｉｎｉｍｕｍｄｅｇｒｅｅｅ（Ｇ）ａｔｌｅａｓｔＺｋ，ｔｈｅｎＧｈａｓａｋ－ｆａｃｔｏｒ．Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｇｅｎｅｒａｌｉｚｅｄｔｈｅｒｅｓｕｌｔｏｆＴｈｅｏｒｅｍＣ，ａｎｄｏｂｔａｉｎｔｈｅｆｏｌｌｏｗｉｎｇＴｈｅｏｒｅｍｉｆＧｉｓａｎＮ＇－ｌｏｃａｌｌｙｃｏｎｎｅｃｔｅｄｃｌａｗｔｈｅｅｇｒａｐｈｗｉｔｈｂ（Ｇ）２２，ｔｈｅｎＧｈａｓａ２－ｆａｃｔｏｒ．２．ＬｅｍｍａｓＬｅｍｍａ１ＩｆＧｉｓａｎＮ＇－ｌｏｃａｌｌｙｃｏｎｎｅｃｔｅｄｃｌａｗ－ａｃｅｇａｓｈｗｉｔｈ６（Ｇ）２２，ｔｈｅｎｆｏｒｅａｃｈｘｏ６Ｖ（Ｇ），Ｇｈａｓａｓｈｏｎｅｓｔｃｙｃｌｅｃｏｎｔａｉｎｉｎｇｘｏａｎｄｈａｖｉｎｇａｔｍｏｓｔ５ｖｅｎｉｃｅｓ．Ｌｅｍｍａ２ＩｆＧｉｓａｎＮ＇－－ｌｏｃａｌｌｙｃｏｎｎｅｃｔｅｄｃｌａｗ－ｆｒ?

3-连通无爪图的周长

设Ｇ为ｎ阶３连通无爪图·δ＝ｍｉｎ｛ｄ（ｘ）｜ｘ∈Ｖ（Ｇ）｝，δ＝ｍｉｎ｛ｍａｘ（ｄ（ｘ），ｄ（ｙ））｜ｘ，ｙ∈Ｖ（Ｇ），ｄ（ｘ，ｙ）＝２｝，则Ｃ（Ｇ）≥ｍｉｎ｛ｎ，３δ＋δ，６δ｝·采用反证法，将图Ｇ分为若干情形·在每一种情形中，利用图Ｇ的３连通性和无爪性，构造若图Ｇ的最长圈不满足已给条件的矛盾·

关于生成迹在闭包运算下的稳定性

证明了如果在图G的闭包中可以找到一个以某确定顶点为端点的生成迹当且仅当在G中可以找到一个以该顶点为端点的生成迹,得出了无爪图中生成迹的存在性在Ryjacek闭包运算下是稳定的,也就是一个无爪图G存在一个生成迹当且仅当图G的闭包cl(G)存在一个生成迹.

3—连通K—正则无爪图中的最长圈

证明了最多含5K个顶点的3-连通、K-正则的无爪图是Hamilton图。

半无爪图的闭包

若对图G中任意一对距离为2的点x,y,存在u∈N(x)∩N(y),使得[u]N[x]∪N[y],则称G为半无爪图.许多关于无爪图的结果已经被推广到更大的图类———半无爪图,本文证明了下面的结果:(1)若G是半无爪图,x是G的一适宜点,G′为由G在x局部完备所得,则G′仍是半无爪图,但G′不一定是无爪图.(2)若G是半无爪图,则其闭包cl(G)是唯一确定的.并由(1)有推论:若G是半无爪图,则其闭包cl(G)仍是半无爪图.

无爪图的周长

设Ｇ为ｎ阶２连通无爪图，δ－ｍｉｎ｛ｄ（ｘ）│ｘ∈Ｖ（Ｇ）｝，δ－ｍｉｎ｛ｍａｘ（ｄ（ｘ）．ｄ（ｙ））│ｘ，ｙｋ∈Ｖ（Ｇ）．ｄ（ｘ，ｙ）＝３｝．则（ｉ）ｃ（ｇ）≥ｍｉｎ｛ｎ．２δ＋４）；（ｉｉ）当δ≥１／２（ｎ－δ－２）时Ｇ是哈密顿图。

三角连通半无爪图的点泛圈性

证明了无孤立点的边数不小于3的三角连通的半无爪图是点泛圈的．

k-连通半无爪图的Hamilton性质

半无爪图是包含无爪图的更大的图类。关于k-连通半无爪图,得到以下结果:G是k-连通的半无爪图(k≥2),如果对于G2的任意基数为k+1的独立集X,都有∑d(v)≥n-k,则G是Hamilton图。

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

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

2-连通无爪图的连通因子(英文)

若图G不含有同构于K1,3的导出子图,则称G为一个无爪图.令a和b是两个整数满足2≤a≤b.本文证明了若G是一个含有[a,b]因子的2连通无爪图,则G有一个连通的[a,b+1]因子.

用周长刻画的超欧拉图

利用超欧拉迭线图的特征,证明了周长不超过7的2-边连通的无爪简单图是超欧拉图.同时也证明了周长为8的2-边连通的无爪简单图只有一个不是超欧拉图.

强N_2-局部连通无爪图的Hamilton性

运用反证法的证明技巧,对任一无爪图G及其圈C,证明了只要C上有一个接触点是强N_2-局部连通的,则C一定不是最长圈.即证明了强N_2-局部连通无爪图是Hamilton图.

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

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

关于无爪图中哈密尔顿圈的一个注记(英文)

证明了具有Hourglass和Dumbbell性质的3-连通的无爪图是哈密尔顿圈.

(k+1)-连通无爪图的Hamilton-连通性

一个图若不含与Ｋ１．３同构的导出子图，则称它为无爪图。本文利用Ｔ－插点方法，得到（ｋ＋１）－连通无爪图是Ｈａｍｉｌｔｏｎ－连通的两个充分条件．（１）设Ｇ是（ｋ＋１）－连通无爪图（ｋ２），若对每个Ｘ∈Ｉｋ＋１（Ｇ），有ｓ２（Ｘ）＞１，则Ｇ是Ｈａｍｉｌｔｏｎ－连通图．（２）设Ｇ是（ｋ＋１）－连通无爪图（ｋ２），若对每个Ｘ∈Ｉｋ＋１（Ｇ），有∑ｘ∈Ｘｄ（ｘ）ｎ（Ｘ）－ｋ＋１，则Ｇ是Ｈａｍｉｌｔｏｎ－连通图．

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

证明了每一个3—连通k—正则无爪图G,当G的点数n≤5k-5时,G包含一个Hamilton圈。