关于(a,b,s)-临界图的邻域条件

设G是一个n阶的图.设a,b和s是整数,使得b＞a≥1.设δ(G)是G的最小度.证明了:如果δ(G)≥(k-1)a+s,n≥(a+b)(k(a+b)-2)/b,并且|Nc(x1)∪NG(x2)∪…∪NG(xk)|≥an/(a+b)+s对V(G)任意的独立子集{x1,x2,…,xk}都成立,这里k≥2,则G是一个(a,b,s)-临界图.这个结果在某种意义上是最好的.

On Neighborhood Condition for Graphs to be(a,b,s)-critical Graph

Let G be a graph of order n,and let a, b and s be integers such that 1≤a ＜ b. Let δ(G) be the minimum degree of G. It is proved that if δ(G)≥(k- 1)a + s,n≥(a + b)(k(a + b) -2)/b, and |NG(x1)∪NG(x2)∪……∪NG(xk)|≥an/(a+b)+s for any independent subset｛x1,x2,…xk｝of V(G),where k ≥2, then G is an (a, b, s)-critical graph. This result is best possible in some sense.