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

Mahjoub, Ali Ridha

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

Number

1-3

Publisher

Elsevier

Pages

209-219

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