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
1995Nom de la revue
Discrete Applied MathematicsVolume
62Numéro
1-3Éditeur
Elsevier
Pages
209-219
Identifiant publication
Métadonnées
Afficher la notice complèteAuteur(s)
Mahjoub, Ali RidhaRésumé (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.Mots-clés
Polytopes; Total dual integrality; Ki-covers; Graphs noncontractible to K5ePublications associées
Affichage des éléments liés par titre et auteur.
-
Mahjoub, Ali Ridha; McCormick, S. Thomas (2010) Article accepté pour publication ou publié
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) Communication / Conférence
-
Thabti, Boulbaba; Lourimi, Ali; Youssef, Habib; Mahjoub, Ali Ridha; Meddeb, Aref (2012) Communication / Conférence
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) Article accepté pour publication ou publié
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2009) Article accepté pour publication ou publié