独立数的一个下界  

作　　者：李雨生[1] C.C.Rousseau 臧文安[3] 

机构地区：[1]河海大学数学物理系,南京210098 [2]Department of Mathe matical Sciences,The University of Memphis [3]香港大学数学系

出　　处：《中国科学（A辑）》2001年第10期865-870,共6页Science in China(Series A)

基　　金：国家自然科学基金 (批准号 :198710 2 3 );教育部优秀年轻教师基金;江苏省"3 3 3"工程基金;香港RGC基金资助项目

摘　　要：设G是一个图 ,其度序列为 (dv) .若由G的任意邻域导出子图的最大度至多为m ,则G的独立数至少是 ∑vfm +1(dv) ,这里当x >0 ,函数fm +1(x)大于log(x/(m + 1 ) ) - 1x .对于加权图G =(V ,E ,w) ,证明了它的加权独立数至少是∑vwv1 +dv,这里wv 是顶点v的权重 .

关 键 词：独立数 离散形式 加权图 图论 导出子图 局部稀疏图 Turan定理 

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