Abstract
Let u, v be distinct vertices of a multigraph G with degrees du and dv, respectively. The number of edge-disjoint u, u-paths in G is bounded above by min{du, dv}. A multigraph G is optimally edge-connected if for all pairs of distinct vertices u and v this upper bound is achieved. If G is a multigraph with degree sequence D, then we say G is a realisation of D. We characterize degree sequences of multigraphs that have an optimally edge-connected realisation as well as those for which every realisation is optimally edge-connected.
| Original language | English |
|---|---|
| Pages (from-to) | 161-168 |
| Number of pages | 8 |
| Journal | Ars Combinatoria |
| Volume | 77 |
| Publication status | Published - Oct 2005 |
| Externally published | Yes |
ASJC Scopus subject areas
- General Mathematics