Show simple item record

A min-max relation for K3-covers in graphs non contractible to K5\e

dc.contributor.authorMahjoub, Ali Ridha
dc.date.accessioned2010-04-30T09:43:07Z
dc.date.available2010-04-30T09:43:07Z
dc.date.issued1995
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/4062
dc.language.isoenen
dc.subjectPolytopesen
dc.subjectTotal dual integralityen
dc.subjectKi-coversen
dc.subjectGraphs noncontractible to K5een
dc.subject.ddc003en
dc.titleA min-max relation for K3-covers in graphs non contractible to K5\een
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn Euler and Mahjoub (1991) it is proved that the triangle-free subgraph polytope of a graph noncontractible to K5e is completely described by the trivial inequalities and the so-called triangle and odd wheel inequalities. In this paper we show that the system denned by those inequalities is TDI for a subclass of that class of graphs. As a consequence we obtain the following min-max relation: If G is a graph noncontractible to K5e, then the minimum number of edges covering all the triangles of G equals the maximum profit of a partition of the edge set of G into edges, triangles and odd wheels. Here the profit of an edge is 0, the profit of a triangle is 1 and the profit of a 2k + 1-wheel (Image is equal to k + 1.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol62en
dc.relation.isversionofjnlissue1-3en
dc.relation.isversionofjnldate1995-09
dc.relation.isversionofjnlpages209-219en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/0166-218X(94)00153-5en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record