On the diameter of the edge cover polytope (Q1115884): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q975520 |
||
| Property / author | |||
| Property / author: Cor A. J. Hurkens / rank | |||
Revision as of 17:28, 21 February 2024
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
