Compositions of Graphs and the Triangle-Free Subgraph Polytope

Bendali, Fatiha; Mailfert, Jean; Mahjoub, Ali Ridha

Bendali, Fatiha; Mailfert, Jean; Mahjoub, Ali Ridha (2002), Compositions of Graphs and the Triangle-Free Subgraph Polytope, Journal of Combinatorial Optimization, 6, 4, p. 359-381. http://dx.doi.org/10.1023/A:1019518830361

Type

Article accepté pour publication ou publié

Date

2002

Nom de la revue

Journal of Combinatorial Optimization

Volume

Numéro

Éditeur

Springer

Pages

359-381

Résumé (EN)

In this paper, we study a composition (decomposition) technique for the triangle-free subgraph polytope in graphs which are decomposable by means of 3-sums satisfying some property. If a graph G decomposes into two graphs G 1 and G 2, we show that the triangle-free subgraph polytope of G can be described from two linear systems related to G 1 and G 2. This gives a way to characterize this polytope on graphs that can be recursively decomposed. This also gives a procedure to derive new facets for this polytope. We also show that, if the systems associated with G 1 and G 2 are TDI, then the system characterizing the polytope for G is TDI. This generalizes previous results in R. Euler and A.R. Mahjoub (Journal of Comb. Theory series B, vol. 53, no. 2, pp. 235–259, 1991) and A.R. Mahjoub (Discrete Applied Math., vol. 62, pp. 209–219, 1995).

Mots-clés

TDI; facet; polytope; triangle-free subgraph; 3-sum; composition of polyhedra