分数ID-消去图的邻域并条件  

Neighborhood Union Conditions for Fractional ID-Deleted Graph

作　　者：高炜[1] 

机构地区：[1]云南师范大学信息学院,云南昆明650092

出　　处：《昆明学院学报》2012年第6期5-9,共5页Journal of Kunming University

基　　金：国家自然科学基金资助项目(60903131);教育部科学技术研究重点资助项目(210210);民族教育信息化教育部重点实验室资助项目

摘　　要：若删除G中任意一个独立集后得到的图依然是分数(g,f,m)-消去图,则称G为分数ID-(g,f,m)-消去图.将若干个关于分数消去图邻域并条件的结论推广到分数ID-消去图,证明了如下两个结论:1)阶为n的图G满足n≥12k+6m-11,δ(G)≥n/3+k+m,且NG(x)∪NG(y)≥(2n)/3对G中任意一对不相邻的顶点x,y都成立,则G是分数ID-(k,m)-消去图;2)若δ(G)≥(an)/(2a+b)+(b2(i-1))/a+2m,n>((2a+b)[i(a+b)+2m-2])/a,且NG(x1)∪…∪NG(xi)≥((a+b)n)/(2a+b),对V(G)的所有独立集{x1,…,xi}都成立.则G是分数ID-(g,f,m)-消去图.A graph G is called a fractional ID-（g,f, m）-deleted graph, if delete any independent set from G, the resulting graph is still a fractional （g,f, m）-deleted graph. In this paper, we extend some results on neighborhood union conditions for fractional deleted graph to fractional ID-deleted graph. It is determined following two results ： 1 ） If graph G with order n satisfies n≥12k ＋ 6m - 11, δ（G） ≥n/3 ＋ k ＋ m and /NG （x） U NG （y） /≥ for any two non-adjacent vertices x,y in G, then G is a fractional ID-（k, m）-deleted graph;2） If δ（G） ≥ an /（a2＋b） ＋b2（i-1）/a ＋2m, n 〉 （2a ＋b）[i（a ＋b） ＋2m-2 ] , and /NG（x1） U …… U NG（xi） ] （a ＋ b）n/2a＋b .for any independent set {x1 ,…… ,xi / in V（G） ,then G is a fractional ID-（g,f,m）-deleted graph.

关 键 词：分数因子 分数消去图 分数ID-消去图 邻域并 

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