On the diameter of the edge cover polytope (Q1115884)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the diameter of the edge cover polytope |
scientific article |
Statements
On the diameter of the edge cover polytope (English)
0 references
1991
0 references
We characterize adjacency of edge covers on the edge cover polytope of a graph \(G=(V,E)\). We find a sharp bound on the distance between two edge covers. Finally we derive that the diameter of the edge cover polytope is equal to \(| E| -\rho (G)\), where \(\rho\) (G) denotes the minimum size of an edge cover of G.
0 references
0-1-polyhedra
0 references
adjacency of vertices
0 references
number of pivots
0 references
simplex method
0 references
edge covers
0 references
edge cover polytope
0 references
