Thumbnail - Request a copy

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

Mahjoub, Ali Ridha (1995), A min-max relation for K3-covers in graphs non contractible to K5\e, Discrete Applied Mathematics, 62, 1-3, p. 209-219. http://dx.doi.org/10.1016/0166-218X(94)00153-5

Type
Article accepté pour publication ou publié
Date
1995
Journal name
Discrete Applied Mathematics
Volume
62
Number
1-3
Publisher
Elsevier
Pages
209-219
Publication identifier
Metadata
Show full item record
Author(s)
Mahjoub, Ali Ridha
Abstract (EN)
In 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.
Subjects / Keywords
Polytopes; Total dual integrality; Ki-covers; Graphs noncontractible to K5e