On an extremal problem related to a theorem of Whitney (Q869580)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On an extremal problem related to a theorem of Whitney |
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
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
vertex-connectivity
0 references
edge-connectivity
0 references
minimum degree
0 references