On an extremal problem related to a theorem of Whitney (Q869580)

From MaRDI portal





scientific article
Language Label Description Also known as
English
On an extremal problem related to a theorem of Whitney
scientific article

    Statements

    On an extremal problem related to a theorem of Whitney (English)
    0 references
    0 references
    0 references
    8 March 2007
    0 references
    A classical result of Whitney states that \(\kappa(G)\leq\lambda(G)\leq\delta(G)\) for each graph \(G\), where \(\kappa(G)\) denotes the vertex-connectivity, \(\lambda(G)\) the edge-connectivity and \(\delta(G)\) the minimum degree of \(G\). For any three positive integers \(a\leq b\leq c\), the authors determine the least order and the least size among all graphs \(G\) such that \(\kappa(G)=a\), \(\lambda(G)=b\) and \(\delta(G)=c\). In addition, they show that there exist graphs of all orders greater or equal to the least order with these properties.
    0 references
    0 references
    vertex-connectivity
    0 references
    edge-connectivity
    0 references
    minimum degree
    0 references

    Identifiers