On the diameter of the edge cover polytope (Q1115884): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q975520 |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
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 |
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