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
TypeArticle accepté pour publication ou publié
Journal nameDiscrete Applied Mathematics
MetadataShow 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 / KeywordsPolytopes; Total dual integrality; Ki-covers; Graphs noncontractible to K5e
Showing items related by title and author.
Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017) Article accepté pour publication ou publié