On the diameter of the edge cover polytope (Q1115884): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 03:32, 31 January 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
    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 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