The cut cone III: On the role of triangle facets
Deza, Michel; Laurent, Monique; Poljak, Svatopluk (1992), The cut cone III: On the role of triangle facets, Graphs and Combinatorics, 8, 2, p. 125-142. http://dx.doi.org/10.1007/BF02350631
Type
Article accepté pour publication ou publiéDate
1992Journal name
Graphs and CombinatoricsVolume
8Number
2Publisher
Springer
Pages
125-142
Publication identifier
Metadata
Show full item recordAbstract (EN)
The cut polytopeP n is the convex hull of the incidence vectors of the cuts (i.e. complete bipartite subgraphs) of the complete graph onn nodes. A well known class of facets ofP n arises from the triangle inequalities:x ij +x ik +x jk ≤2 andx ij −x ik −x jk ≤0 for 1≤i, j, k≤n. Hence, the metric polytopeM n , defined as the solution set of the triangle inequalities, is a relaxation ofP n .We consider several properties of geometric type forP n , in particular, concerning its position withinM n . Strengthening the known fact ([3]) thatP n has diameter 1, we show that any set ofk cuts,k≤log2 n, satisfying some additional assumption, determines a simplicial face ofMn and thus, also, ofP n . In particular, the collection of low dimension faces ofP n is contained in that ofM n . Among a large subclass of the facets ofP n , the triangle facets are the closest ones to the barycentrum ofP n and we conjecture that this result holds in general. The lattice generated by all even cuts (corresponding to bipartitions of the nodes into sets of even cardinality) is characterized and some additional questions on the links between general facets ofP n and its triangle facets are mentioned.Subjects / Keywords
graphsRelated items
Showing items related by title and author.
-
Deza, Michel; Laurent, Monique (1992) Article accepté pour publication ou publié
-
Deza, Michel; Laurent, Monique (1992) Article accepté pour publication ou publié
-
Laurent, Monique; Deza, Michel (1989) Article accepté pour publication ou publié
-
Laurent, Monique; Deza, Michel (1989) Article accepté pour publication ou publié
-
Laurent, Monique; Sassano, Antonio (1992) Article accepté pour publication ou publié