×

Degree sequences of optimally edge-connected multigraphs. (English) Zbl 1164.05334

A multigraph is said to be optimally edge-connected if for every pair of vertices \(u,v\), the maximum number of edge-disjoint paths joining \(u\) to \(v\) equals the smaller of the degrees of \(u\) and \(v\). A multigraph with degree sequence \(D\) is called a realization of \(D\). The authors characterize the degree sequences that have an optimally edge-connected realization, as well as those for which every realization is optimally edge-connected.

MSC:

05C07 Vertex degrees
05C40 Connectivity
PDFBibTeX XMLCite