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
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?
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
2011 Impact Factor: 0.701
2012 SCImago Journal Rankings: 0.540
References

 

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