Show simple item record

Compositions of Graphs and the Triangle-Free Subgraph Polytope

dc.contributor.authorBendali, Fatiha
HAL ID: 172499
dc.contributor.authorMailfert, Jean
HAL ID: 20286
dc.contributor.authorMahjoub, Ali Ridha
dc.date.accessioned2010-04-13T15:37:43Z
dc.date.available2010-04-13T15:37:43Z
dc.date.issued2002
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3962
dc.language.isoenen
dc.subjectTDIen
dc.subjectfaceten
dc.subjectpolytopeen
dc.subjecttriangle-free subgraphen
dc.subject3-sumen
dc.subjectcomposition of polyhedraen
dc.subject.ddc511en
dc.titleCompositions of Graphs and the Triangle-Free Subgraph Polytopeen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn 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).en
dc.relation.isversionofjnlnameJournal of Combinatorial Optimization
dc.relation.isversionofjnlvol6en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate2002-12
dc.relation.isversionofjnlpages359-381en
dc.relation.isversionofdoihttp://dx.doi.org/10.1023/A:1019518830361en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelPrincipes généraux des mathématiquesen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record