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

The lower bound on independence number

Authors:	Li Yusheng Cecil C.ROUSSEAU ZANG Wen'an

Affiliation:	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 $sumlimits_v {f_{m + 1} left( {d_v } right)}$ , where f_m+1( x) is a function greater than $frac{{logleft( {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 $sumlimits_v {frac{{w_v }}{{1 + d_v }}}$ where w_v is the weight of v.

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