The lower bound on independence number期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

The lower bound on independence number

Authors:	Li Yusheng Cecil CROUSSEAU ZANG Wen'an

Institution:	1. Department of Mathematics,Hohai University,Nanjing 210098,China 2. Department of Mathematical Sciences,the University of Memphis,Memphis,TN 38152,USA 3. Department of Mathematics,the University of Hong Kong,Hong Kong,China

Abstract:	Let G be a graph with degree sequence ( d_v). 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 f_m+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 w_v is the weight of v.

Keywords:	independence number discrete form weighted graph
本文献已被万方数据 SpringerLink 等数据库收录！