-
题名2─连通图中X─最长圈下界估计(英文)
- 1
-
-
作者
罗红
蔡光程
-
机构
云南大学成人教育学院
昆明理工大学基础部
-
出处
《云南民族学院学报（自然科学版）》
2000年第1期9-12,17,共5页
-
文摘
给一个图Ｇ，ＸＶ（Ｇ），Ｇ［Ｘ］为Ｇ的Ｘ生成子图，ｒ为正整数。定义α（Ｘ）＝ｍａｘ｛｜Ｓ｜｝Ｓ是Ｇ［Ｘ］的顶点独立集｝，αｋ（Ｘ）＝ｍｉｎ｛∑ｄ（ｖｉ）｜｛ｖ１，ｖ２，…，ｖｋ｝是Ｇ［Ｘ］的顶点独立集｝，ＮＣｋ（Ｘ）＝ｍｉｎ｛｜Ｕｋｉ＝１；Ｎ（ｖｉ）｜（ｖ１，…，ｖｋ是Ｇ［ｘ］的独点独立集｝（ｋ≥２）．我们得到结论；对—任意的ｎ阶２─连通图Ｇ（ｎ≥３），ｘＧ，且σ３（Ｘ）≥ｎ＋ｒ≥ｎ＋２，则存在一个包含Ｘ的顶点数为ｍｉｎ｛｜Ｘ｜，｜Ｘ｜＋ＮＣｒ＋２＋ｅ（ｎ＋ｒ）（Ｘ）－α（Ｘ）｝的圈，ε（ｉ）＝３（ｉ）ｉ．该结论推广了Ｈ．Ｊ．Ｂｒｏｅｒｓｍａ在文献［１］中的结果．
-
关键词
x-最长圈
x-控制圈
2-连通图
下界
估计
-
Keywords
x-longest cycle, x-dominating cycle, 2-Connected Graph
-
分类号
O157.5
[理学—数学]
-
-
题名X-最长圈的下界估计
- 2
-
-
作者
罗红
梁立
-
机构
云南大学成人教育学院
云南师范大学计算机系
-
出处
《云南大学学报（自然科学版）》
CAS
CSCD
2000年第3期169-171,共3页
-
基金
云南省教委自然科学基金资助项目!( 964 10 91)
-
文摘
设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个顶点的独立集 .
-
关键词
1-坚韧图
x-最长圈
x-控制圈
连通图
下界
估计
-
Keywords
tough graph
x -longest cycle
x -domination cycle
-
分类号
O157.5
[理学—数学]
-
