File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1360/02ys9006
 Scopus: eid_2s2.00036376163
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Article: The lower bound on independence number
Title  The lower bound on independence number 

Authors  
Keywords  Discrete form Independence number Weighted graph 
Issue Date  2002 
Publisher  Science in China Press. The Journal's web site is located at http://www.scichina.com:8081/sciAe/EN/volumn/current.shtml 
Citation  Science In China, Series A: Mathematics, Physics, Astronomy, 2002, v. 45 n. 1, p. 6469 How to Cite? 
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 ∑ vf m+1(d v), where f m+1(x) is a function greater than log(x/(m+1))  1/x 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 ∑ v w v/1 + d v where w v is the weight of v. 
Persistent Identifier  http://hdl.handle.net/10722/75353 
ISSN  2011 Impact Factor: 0.701 2012 SCImago Journal Rankings: 0.540 
References 
DC Field  Value  Language 

dc.contributor.author  Li, Y  en_HK 
dc.contributor.author  Rousseau, CC  en_HK 
dc.contributor.author  Zang, W  en_HK 
dc.date.accessioned  20100906T07:10:19Z   
dc.date.available  20100906T07:10:19Z   
dc.date.issued  2002  en_HK 
dc.identifier.citation  Science In China, Series A: Mathematics, Physics, Astronomy, 2002, v. 45 n. 1, p. 6469  en_HK 
dc.identifier.issn  10069283  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/75353   
dc.description.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 ∑ vf m+1(d v), where f m+1(x) is a function greater than log(x/(m+1))  1/x 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 ∑ v w v/1 + d v where w v is the weight of v.  en_HK 
dc.language  eng  en_HK 
dc.publisher  Science in China Press. The Journal's web site is located at http://www.scichina.com:8081/sciAe/EN/volumn/current.shtml  en_HK 
dc.relation.ispartof  Science in China, Series A: Mathematics, Physics, Astronomy  en_HK 
dc.subject  Discrete form  en_HK 
dc.subject  Independence number  en_HK 
dc.subject  Weighted graph  en_HK 
dc.title  The lower bound on independence number  en_HK 
dc.type  Article  en_HK 
dc.identifier.openurl  http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=00368237&volume=45&spage=64&epage=69&date=2002&atitle=The+Lower+Bound+on+Independence+Number  en_HK 
dc.identifier.email  Zang, W:wzang@maths.hku.hk  en_HK 
dc.identifier.authority  Zang, W=rp00839  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.doi  10.1360/02ys9006   
dc.identifier.scopus  eid_2s2.00036376163  en_HK 
dc.identifier.hkuros  66883  en_HK 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.00036376163&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  45  en_HK 
dc.identifier.issue  1  en_HK 
dc.identifier.spage  64  en_HK 
dc.identifier.epage  69  en_HK 
dc.publisher.place  China  en_HK 
dc.identifier.scopusauthorid  Li, Y=7502087425  en_HK 
dc.identifier.scopusauthorid  Rousseau, CC=7102137402  en_HK 
dc.identifier.scopusauthorid  Zang, W=7005740804  en_HK 