File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: The lower bound on independence number

TitleThe lower bound on independence number
Authors
Li, YRousseau, CCZang, W
KeywordsDiscrete form
Independence number
Weighted graph
Issue Date2002
PublisherScience 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. 64-69 How to Cite?
DOI: http://dx.doi.org/10.1360/02ys9006
AbstractLet 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 Identifierhttp://hdl.handle.net/10722/75353
ISSN
1006-9283
2011 Impact Factor: 0.701
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorLi, Yen_HK
dc.contributor.authorRousseau, CCen_HK
dc.contributor.authorZang, Wen_HK
dc.date.accessioned2010-09-06T07:10:19Z-
dc.date.available2010-09-06T07:10:19Z-
dc.date.issued2002en_HK
dc.identifier.citationScience In China, Series A: Mathematics, Physics, Astronomy, 2002, v. 45 n. 1, p. 64-69en_HK
dc.identifier.issn1006-9283en_HK
dc.identifier.urihttp://hdl.handle.net/10722/75353-
dc.description.abstractLet 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.languageengen_HK
dc.publisherScience in China Press. The Journal's web site is located at http://www.scichina.com:8081/sciAe/EN/volumn/current.shtmlen_HK
dc.relation.ispartofScience in China, Series A: Mathematics, Physics, Astronomyen_HK
dc.subjectDiscrete formen_HK
dc.subjectIndependence numberen_HK
dc.subjectWeighted graphen_HK
dc.titleThe lower bound on independence numberen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0036-8237&volume=45&spage=64&epage=69&date=2002&atitle=The+Lower+Bound+on+Independence+Numberen_HK
dc.identifier.emailZang, W:wzang@maths.hku.hken_HK
dc.identifier.authorityZang, W=rp00839en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1360/02ys9006-
dc.identifier.scopuseid_2-s2.0-0036376163en_HK
dc.identifier.hkuros66883en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0036376163&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume45en_HK
dc.identifier.issue1en_HK
dc.identifier.spage64en_HK
dc.identifier.epage69en_HK
dc.publisher.placeChinaen_HK
dc.identifier.scopusauthoridLi, Y=7502087425en_HK
dc.identifier.scopusauthoridRousseau, CC=7102137402en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats