File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Packing cycles in graphs

TitlePacking cycles in graphs
Authors
Ding, GZang, W
Issue Date2002
PublisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jctb
Citation
Journal Of Combinatorial Theory. Series B, 2002, v. 86 n. 2, p. 381-407 How to Cite?
DOI: http://dx.doi.org/10.1006/jctb.2002.2134
AbstractA graph G is called cycle Mengerian (CM) if for all nonnegative integral function w defined on V(G), the maximum number of cycles (repetition is allowed) in G such that each vertex v is used at most w(v) times is equal to the minimum of ∑ {w(x) : x ∈ X}, where the minimum is taken over all X ⊆ V(G) such that deleting X from G results in a forest. The purpose of this paper is to characterize all CM graphs in terms of forbidden structures. As a corollary, we prove that if the fractional version of the above minimization problem always have an integral optimal solution, then the fractional version of the maximization problem will always have an integral optimal solution as well. 2002 Elsevier Science (USA).
Persistent Identifierhttp://hdl.handle.net/10722/75346
ISSN
0095-8956
2021 Impact Factor: 1.491
2020 SCImago Journal Rankings: 1.686
ISI Accession Number ID
WOS:000178979600011
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorDing, Gen_HK
dc.contributor.authorZang, Wen_HK
dc.date.accessioned2010-09-06T07:10:15Z-
dc.date.available2010-09-06T07:10:15Z-
dc.date.issued2002en_HK
dc.identifier.citationJournal Of Combinatorial Theory. Series B, 2002, v. 86 n. 2, p. 381-407en_HK
dc.identifier.issn0095-8956en_HK
dc.identifier.urihttp://hdl.handle.net/10722/75346-
dc.description.abstractA graph G is called cycle Mengerian (CM) if for all nonnegative integral function w defined on V(G), the maximum number of cycles (repetition is allowed) in G such that each vertex v is used at most w(v) times is equal to the minimum of ∑ {w(x) : x ∈ X}, where the minimum is taken over all X ⊆ V(G) such that deleting X from G results in a forest. The purpose of this paper is to characterize all CM graphs in terms of forbidden structures. As a corollary, we prove that if the fractional version of the above minimization problem always have an integral optimal solution, then the fractional version of the maximization problem will always have an integral optimal solution as well. 2002 Elsevier Science (USA).en_HK
dc.languageengen_HK
dc.publisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jctben_HK
dc.relation.ispartofJournal of Combinatorial Theory. Series Ben_HK
dc.titlePacking cycles in graphsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0095-8956&volume=86&spage=381&epage=407&date=2002&atitle=Packing+Cycles+in+Graphsen_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.1006/jctb.2002.2134en_HK
dc.identifier.scopuseid_2-s2.0-0036847554en_HK
dc.identifier.hkuros76701en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0036847554&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume86en_HK
dc.identifier.issue2en_HK
dc.identifier.spage381en_HK
dc.identifier.epage407en_HK
dc.identifier.isiWOS:000178979600011-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridDing, G=7201791806en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK
dc.identifier.citeulike36787-
dc.identifier.issnl0095-8956-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats