Compositions of Graphs and the Triangle-Free Subgraph Polytope
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
2002Journal name
Journal of Combinatorial OptimizationVolume
6Number
4Publisher
Springer
Pages
359-381
Publication identifier
Metadata
Show full item recordAbstract (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).Subjects / Keywords
TDI; facet; polytope; triangle-free subgraph; 3-sum; composition of polyhedraRelated items
Showing items related by title and author.
-
Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha (2010) Article accepté pour publication ou publié
-
Bendali, Fatiha; Mahjoub, Ali Ridha; Mailfert, Jean; Diarrassouba, Ibrahima (2010) Article accepté pour publication ou publié
-
Bendali, Fatiha; Ibrahima, Diarrassouba; Didi Biha, Mohamed; Mahjoub, Ali Ridha; Mailfert, Jean (2006) Communication / Conférence
-
Barahona, Francisco; Fonlupt, Jean; Mahjoub, Ali Ridha (1994) Article accepté pour publication ou publié
-
Barahona, Francisco; Mahjoub, Ali Ridha (1994) Article accepté pour publication ou publié