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.