关于图是(r,n)-临界图的一个邻域条件

设n，m和r是满足r≥2，n≥0，m≥3的整数，且当r是奇数时，假设r≥m-1．称一个图为K1,m-free，如果它不包含以Kt,m为导出的子图．称一个图G为一个（r,n）-临界图，如果在删去G的任意n个点后，剩下G的子图都有一个r-因子,设G是一个Kl,m-free的（n＋1）-连通图，且阶为｜G｜以及r（｜G｜≥n）是偶数,证明了：如果G的最小度至少是r＋n＋m-1，阶｜G｜≥8r5＋n，并且对V（G）的任意独立点集{x1，x2}都有｜NG（x1）∪NG（x2）｜≥（｜G｜＋n）／2，那么G是一个（r,n）-临界图．关于G的最小度和｜NG（x1）∪NG（X2）｜的下界是紧的。

A Neighborhood Condition for Graphs to be (r, n)-Critical Graphs

Let n, m and r be integers with r ≥ 2, n ≥ 0, m ≥ 3 and if r is odd suppose that r ≥ m - 1. A graph is called K1.m-free if it contains no K1,m as an induced subgraph. A graph G is called an (r, n)-critical graph if after deleting any n vertices of G the remaining graph of G has an r-factor. Let G be a (n+ 1)-connected K1,m-free graph of order |G| with r(|G|- n) even. It is proved that if the minimum degree of G is at least r + n + m- 1, the order |G| ≥ 8r - 5 + n, and |NG(x1) ∪ NG(x2)| ≥ (|G| + n)/2 for any independent subset {x1, x2} of V(G), then G is an (r,n)-critical graph. The lower bounds on the minimum degree of G and |NG(x1) ∪ NG(x2)| are sharp.