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

Jian Li · 2003

Let G be a graph of order TBn,and let a, b and s be integers such that 1≤ab. 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 |NG(x1)∪NG(x2)∪...∪NG(xk)|≥an/(a+b)+s for any independent subset {x1,x2,...,xk} of V(G), where k≥2, then G is an (a,b,s)critical graph. This result is best possible in some sense.

Read the paper · More papers on PaperTik