论文部分内容阅读
一个图G在一顶点x处的局部子图L{x}是由G的给定性质定义的包含x的子图L1,并以x为根,例如在点x处的k-局部子图是以x为根,以所有到x距离不超过k的顶点集合{u∈V(G):dG(v,x)≤k}为顶点集;以{uv∈E(G):dG(u,x)〈k,或dG(v,x)〈k}为边集的带根子图。本文证明了:对于G的局部子图L{x},如果每个L{x},x∈V(G),的顶点数(或边数)都小于G的顶点数(边数)减