论文部分内容阅读
设G是一个图,其度序列为(dv). 若由G的任意邻域导出子图的最大度至多为m, 则G的独立数至少是∑vfm+1(dv),$ 这里当x>0, 函数fm+1(x)大于(log(x/(m+1))-1)/(x). 对于加权图G=(V,E,w), 证明了它的加权独立数至少是$∑v(wv)/(1+dv),$ 这里wv是顶点v的权重.