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