Graphic vertices of the metric polytope
type: Item
instance of: scholarly article
title: Graphic vertices of the metric polytope
zbMATH Open document ID: 0854.05095
DOI: 10.1016/0012-365X(94)00091-V
author: Monique Laurent
published in: Discrete Mathematics
publication date: 1996-07-03T00:00:00Z
review text: The paper studies the polytope called the metric polytope \(\text{MP}_n\) defined by the triangle inequalities: \(x_{ij}- x_{ik}- x_{jk}\leq 0\) and \(x_{ij}+ x_{ik}+ x_{jk}\leq 2\) for all \(i, j, k\in \{1, 2,\dots, n\}\). It studies the fractional vertices of \(\text{MP}_n\), many of which are constructed from graphs. Several constructions for one-third-integral vertices are presented, and, in particular, the graphic vertices arising from the suspension of a tree are characterized. The paper describes the symmetries of \(\text{MP}_n\) and obtains that the vertices are partitioned into switching classes. It is shown that, with the exception of the cuts which are pairwise adjacent, no two vertices of the same switching class are adjacent on \(\text{MP}_n\). In fact, all the vertices of \(\text{MP}_n\) for \(n\leq 6\) are described.
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 896536
zbMATH Keywords: polytope
zbMATH Keywords: graphic vertices
zbMATH Keywords: switching class
MaRDI profile type: Publication
cites work: Q3934399
cites work: Extremal Metrics Induced by Graphs
cites work: On the Extreme Rays of the Metric Cone
cites work: The cut cone,L1 embeddability, complexity, and multicommodity flows
cites work: On cuts and matchings in planar graphs
cites work: On the cut polytope
cites work: Q4309968
cites work: Q3974968
cites work: The cut cone. III: On the role of triangle facets
cites work: Information Bounds Are Weak in the Shortest Distance Problem
cites work: Computing extreme rays of the metric cone for seven points
cites work: Weakly bipartite graphs and the max-cut problem
cites work: One-third-integrality in the max-cut problem
cites work: Q3856789
cites work: Combinatorial approaches to multiflow problems
cites work: The Boolean quadratic polytope: Some characteristics, facets and relatives
cites work: Q3137209
description: scientific article; zbMATH DE number 896536