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
TypeArticle accepté pour publication ou publié
Journal nameJournal of Combinatorial Optimization
MetadataShow full item record
Abstract (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 / KeywordsTDI; facet; polytope; triangle-free subgraph; 3-sum; composition of polyhedra
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; Ibrahima, Diarrassouba; Didi Biha, Mohamed; Mahjoub, Ali Ridha; Mailfert, Jean (2006) Communication / Conférence