1坚韧图最长圈的新的充分条件

设G是 p阶l坚韧图。本文证明:如果对任意d(u,v)=2的u,v∈V(G),有max{d(u),d(v)}≥b,则除图Y_1,Y_2,Y_3外,G包含一个长至少为min{p,2b+2}的圈,且是最好可能的。

关于1坚韧图的最长圈

令G 是 p 阶 1坚韧图,且λ=min{d(u)+d(v))|u,v∈V(G);uv∈E},δ=min{d(u)|u∈V(G)},本文证明G的周长 c(G)=p,若 P≤2λ-2δ+2;c(G)≥2λ-2δ+2,若 p>2λ-2δ+2。对某些图来说 c(G)的下界是可以达到的。

1坚韧图的哈密顿性

设G是 p阶1坚韧图,且δ=min{d(u)|u∈V(G)},证明了,若δ≥max{a,p/3},则G 是哈密顿图;若 δ≥(1/3)(p-2+x),则G 是哈密顿图。

1坚韧图中过给定点子集的圈

设Ｇ是阶１－坚韧图，Ｘ是Ｇ的顶点子集合，定义（Ｘ）＝ｍａｘ｛│Ｓ││Ｓ是秀导子图Ｇ［Ｘ］中的顶点独立集｝，σｋ（Ｘ）－ｍｉｎ｛Σ＾ｋｉ＝１（１，２，…ｋ｝是独立集｝和ｃ（Ｘ）＝ｍａｘ｛│Ｖ（Ｃ）∩Ｘ││Ｃ是Ｇ中的圈｝。我们得到如下主要结果：设Ｇ是阶１－坚韧图，并且σ３（Ｘ）≥，则ｃ（Ｘ）≥ｍｉｎ｛│Ｘ│，│Ｘ│＋δ＾－（Ｘ）－α（Ｘ）＋１│，并且这下界是最好的。

1-坚韧图中具有邻域并型的X-最长圈

设 G是连通图 ,X V( G) ,G[X]是 G的 X生成子图 .记α( X) =max{|S|:S是 G[X]的顶点独立集 },σk( X) =min{ ki=1d( vi) :{v1,v2 ,… ,vk}是 G[X]的顶点独立集 },N Ck( X) =min{|∪ki=1N ( vi) |:{v1,v2 ,… ,vk}是 G[X ]的顶点独立集 }( k≥ 2 ) .本文得到如下结果 :对于 n阶的 1 -坚韧图 ( n≥ 3 ) ,X V( G)且σ3 ( X )≥ n+r≥ n,r为正整数 ,则存在一个圈 C满足 |C( X ) |≥ min{|X|,|X|+N Cr+ 5+ε(n+ r) ( X ) -α( X ) },其中ε( i) =3 13 i -13 i.此结果推广了 H.J.Broersma等在文献 [2 ]中的结果 .

1—坚韧Hamilton图的充分条件

设n≥3阶1—坚韧图，若对于G中任意导出爪K(1．3)或变爪K(1．3)＋e上的三点u，v，w，且d（u，v）＝d（u，w）＝2，均满足｜N（u）∩N（v）｜≥-α－1或｜N（u）∩N（w）｜≥α－1，则G是Hamilton图。

一类非Hamilton图的结构

一类非Ｈａｍｉｌｔｏｎ图的结构王江鲁（山东师范大学数学系，２５００１４，济南；３９岁，男，讲师）本文证明下述结论：设Ｇ是非１—坚韧图，则下述三条等价：１）Ｇ是极大非Ｈ—图；２）Ｇ是极大非１—坚韧图；３）。本文所讨论的图是有限无向简单图，所使用的符号和...

X-最长圈的下界估计

设G是连通图 ,X V(G) ,G[X]是G的X生成子图 .记σk(X) =min{ ∑ki =1d(vi) :{v1,v2 ,… ,vk}是G[X]的顶点独立集 } ,得到如下结果 :对于n阶的 1-坚韧图 (n≥ 3) ,X V(G) ,且σ3 (X) ≥n +r≥n ,3｜X｜- 2n≥ 8t- 6r- 17,则存在一个圈C满足｜C(X) ｜≥ { ｜X｜ ,｜N(It) ∩X｜+｜N(It) ∩V(C)｜} ,其中It 是X中t个顶点的独立集 .