Degree Sequences of Optimally Edge-Connected Multigraphs

Abstract

Let $u,v$ be distinct vertices of a multigraph $G$ with degrees $d_u$ and $d_v$, respectively. The number of edge-disjoint $u,v$-paths in $G$ is bounded above by $min\{d_u,d_v\}$. 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 characterise degree sequences of multigraphs that have an optimally edge-connected realisation as well as those for which every realisation is optimally edge-connected.