一类特殊坚韧图的性质

连通图G的坚韧度定义为。如果G的坚韧度是t,并且删去G的任意一条边后其坚韧度减小,则称G是极小t-坚韧的。Matthews等证明了K1,3-free图的连通度是其坚韧度的2倍。本文证明了坚韧度为t的K1,n-free图的连通度不超过(n-1)t,且极小1-坚韧,K1,4-free图的连通度为2。此外,Kriesell猜想极小1-坚韧图的最小度是2。Katona等推广了上述猜想,极小t-坚韧图的最小度是 。本文证明了极小1/(n-1)-坚韧,K1,n-free图的最小度为1,其中n≥3。

大次和的1－坚韧图中的最长圈

给一个图Ｇ，定义，是Ｇ的无关集，是Ｇ中使的无关集，本文证明了：设Ｇ是ｎ阶１－坚韧图，如果σｓ３≥ｎ。，则Ｇ包含长度至少为ｍｉｎ的圈。这个结果推广了若干已知结果，也解决了Ｂｒｏｅｒｓｍａ－Ｈｅｕｖｅｌ－Ｖｅｌｄｍａｎ所提猜想的一个特例．

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坚韧图最长圈的新的充分条件

设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 是哈密顿图。

4-连通、1-坚韧图中的控制圈

设G为4-连通1-坚韧的n阶非Ham ilton图,C为G的最长圈,若σ5(G)≥n+C(G)-1,则C是G的控制圈.

几类极小t-坚韧图的构造

若图G的坚韧度为t,且删除G中任意一条边后坚韧度减小,则称图G是极小t-坚韧的。构造极小t-坚韧图并研究其结构特性在理论和应用上都具有重要意义。证明了几类笛卡尔积图和线图的极小t-坚韧性,并构造出一类k-正则的极小k/2-坚韧图。

4-连通、高次、1-坚韧图的周长

通过研究4-连通、1-坚韧图中控制圈,给出了4-连通、高次、1-坚韧图周长的下界.设G为4-连通、1-坚韧的n阶图,n≥20且σ5(G)≥n+C(G)-1,则有C(G)≥min{n,n+σ5(G)5-α(G)}.

3-连通、高次和坚韧图周长的估计(Ⅰ)

设G是一个n阶3-连通图,周长为C(G),独立数为,若G是1-坚韧的,且,则G的每一个最长圈是控制圈且;又若G是5/3-坚韧的或,则G是Hamilton图。

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图。

论图的坚韧度(Ⅱ)

连通图G的坚韧度,记作τ(G),定义为τ(G)=min{|S|/ω(G-S);S∈C(G)},其中ω(G-S)表示图G-S的连通分支数,C(G)表示图G中所有点割集构成的集合。本文解决了坚韧度τ(G)=τ的p阶连通图G可能具有的最大边数及相应图构造的方法和步骤。

一类非Hamilton图的结构

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

Bondy定理的改进(英文)

设Ｇ是一个ｎ阶ｋ连通图（ｋ≥２）．于１９８０年Ｊ．Ａ．Ｂｏｎｄｙ证明：若ｋ＋１＞（ｋ＋１）（ｎ—１）／２，则Ｇ是Ｈａｍｉｌｔｏｎ图．本文证明对于坚韧图 Ｇ，若ｋ＋１≥（ｋ＋１）（ｎ－３）／２，则 Ｇ是Ｈａｍｉｌｔｏｎ图．

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个顶点的独立集 .

Edge-Tenacity in Graphs

The edge-tenacity of a graph G(V,E) is denned as min{(|S|+T(G-S))/ω(G-S):S(?)E(G)},where T(G ?S) and ω(G-S), respectively, denote the order of the largest component and the number of the components of G-S. This is a better parameter to measure the stability of a network G, as it takes into account both the quantity and the order of components of the graph G-S. In a previous work, we established a necessary and sufficient condition for a graph to be edge-tenacious. These results are applied to prove that K-trees are strictly edge-tenacious. A number of results are given on the relation of edge-tenacity and other parameters, such as the higher-order edge toughness and the edge-toughness.