Let G be a graph with degree sequence ( dv). If the maximum degree of any subgraph induced by a neighborhood of G is at most m, then the independence number of G is at least $\sum\limits_v {f_{m + 1} \left( {d_v } \ri...Let G be a graph with degree sequence ( dv). If the maximum degree of any subgraph induced by a neighborhood of G is at most m, then the independence number of G is at least $\sum\limits_v {f_{m + 1} \left( {d_v } \right)} $ , where fm+1( x) is a function greater than $\frac{{log\left( {x/\left( {m + 1} \right)} \right) - 1}}{x}for x > 0$ for x> 0. For a weighted graph G = ( V, E, w), we prove that its weighted independence number (the maximum sum of the weights of an independent set in G) is at least $\sum\limits_v {\frac{{w_v }}{{1 + d_v }}} $ where wv is the weight of v.展开更多
基金Li is supported in part by the National Natural Science Foundation of China (Grant No. 19871023) Science Foundation of the Education Ministry of China "333" Foundation and NSF of Jiangsu Province. Zang is supported in part by an RGC earmarked researc
文摘Let G be a graph with degree sequence ( dv). If the maximum degree of any subgraph induced by a neighborhood of G is at most m, then the independence number of G is at least $\sum\limits_v {f_{m + 1} \left( {d_v } \right)} $ , where fm+1( x) is a function greater than $\frac{{log\left( {x/\left( {m + 1} \right)} \right) - 1}}{x}for x > 0$ for x> 0. For a weighted graph G = ( V, E, w), we prove that its weighted independence number (the maximum sum of the weights of an independent set in G) is at least $\sum\limits_v {\frac{{w_v }}{{1 + d_v }}} $ where wv is the weight of v.
