2─连通图中X─最长圈下界估计(英文)  

An Improvement of Lower Bound of the X-Longest Cycle in 2-Connected Graph

作　　者：罗红[1] 蔡光程[2] 

机构地区：[1]云南大学成人教育学院,昆明650091 [2]昆明理工大学基础部,昆明650093

出　　处：《云南民族学院学报（自然科学版）》2000年第1期9-12,17,共5页Journal of Yunnan University of The Nationalities(Natural Sciences Edition)

摘　　要：给一个图Ｇ，ＸＶ（Ｇ），Ｇ［Ｘ］为Ｇ的Ｘ生成子图，ｒ为正整数。定义α（Ｘ）＝ｍａｘ｛｜Ｓ｜｝Ｓ是Ｇ［Ｘ］的顶点独立集｝，αｋ（Ｘ）＝ｍｉｎ｛∑ｄ（ｖｉ）｜｛ｖ１，ｖ２，…，ｖｋ｝是Ｇ［Ｘ］的顶点独立集｝，ＮＣｋ（Ｘ）＝ｍｉｎ｛｜Ｕｋｉ＝１；Ｎ（ｖｉ）｜（ｖ１，…，ｖｋ是Ｇ［ｘ］的独点独立集｝（ｋ≥２）．我们得到结论；对—任意的ｎ阶２─连通图Ｇ（ｎ≥３），ｘＧ，且σ３（Ｘ）≥ｎ＋ｒ≥ｎ＋２，则存在一个包含Ｘ的顶点数为ｍｉｎ｛｜Ｘ｜，｜Ｘ｜＋ＮＣｒ＋２＋ｅ（ｎ＋ｒ）（Ｘ）－α（Ｘ）｝的圈，ε（ｉ）＝３（ｉ）ｉ．该结论推广了Ｈ．Ｊ．Ｂｒｏｅｒｓｍａ在文献［１］中的结果．For a graph G and X V(G), let G[X] be the subgraph of G induced by X and r an integer. We define the parameters a(X)=max{|S||S is an independent set of vertices of G[X]}, σ_k,(X)=min{∑~k_i=1 d(v_i)| {v_1, v_2, …, v_k} is an independent set of G[X]} and NC_k(X)=min{|U^k_i=1,,N (v_i)||{v_1,…,v_k} is an independent set of G[X]} (k≥2). It is shown that every 2 -connected graph G of order n (≥ 3) and X G with σ_3(X)> n + r≥ n + 2has a cycle containing at least min{|X|, |X| + NG_r+2+e+(n+r),(X) - a(X)} vertices of X,where (i)=3[1/3i]-1/3i.

关 键 词：X-最长圈 X-控制圈 2-连通图 下界 估计 

分 类 号：O157.5[理学—数学]