Degree sequences of optimally edge-connected multigraphs

Peter Dankelmann, Ortrud Oellermann

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

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 languageEnglish
Pages (from-to)161-168
Number of pages8
JournalArs Combinatoria
Volume77
Publication statusPublished - Oct 2005
Externally publishedYes

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Degree sequences of optimally edge-connected multigraphs'. Together they form a unique fingerprint.

Cite this