• français
    • English
  • français 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Compositions of Graphs and the Triangle-Free Subgraph Polytope

Thumbnail
Date
2002
Dewey
Principes généraux des mathématiques
Sujet
TDI; facet; polytope; triangle-free subgraph; 3-sum; composition of polyhedra
Journal issue
Journal of Combinatorial Optimization
Volume
6
Number
4
Publication date
12-2002
Article pages
359-381
Publisher
Springer
DOI
http://dx.doi.org/10.1023/A:1019518830361
URI
https://basepub.dauphine.fr/handle/123456789/3962
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Bendali, Fatiha
Mailfert, Jean
Mahjoub, Ali Ridha
Type
Article accepté pour publication ou publié
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).

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.