On the diameter of the edge cover polytope (Q1115884): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
| (4 intermediate revisions by 3 users not shown) | |||
| Property / author | |||
| Property / author: Cor A. J. Hurkens / rank | |||
| Property / author | |||
| Property / author: Cor A. J. Hurkens / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q5675543 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3211341 / rank | |||
Normal rank | |||
| links / mardi / name | links / mardi / name | ||
Latest revision as of 14:09, 19 June 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
