Construction of Super Edge-Connected Multigraphs with Prescribed Degrees

Abstract

Let $G=(V,E)$ be a connected multigraph with order $n$. $\delta (G)$ and $\lambda (G)$ are the minimum degree and edge connectivity, respectively. The multigraph $G$ is called maximally edge-connected if $\lambda (G)=\delta (G)$ and super edge-connected if every minimum edge-cut consists of edges incident with a vertex of minimum degree. A sequence $D=(d_1,d_2,\dots ,d_n)$ with $d_1\ge d_2\ge \dots \ge d_n$ is called a multigraphic sequence if there is a multigraph with vertices $v_1,v_2,\dots ,v_n$ such that $d(v_i)=d_i$ for each $i=1,2,\dots ,n$. The multigraphic sequence $D$ is super edge-connected if there exists a super edge-connected multigraph $G$ with degree sequence $D$. In this paper, we present that a multigraphic sequence $D$ with $d_n=1$ is super edge-connected if and only if $\sum _{i=1}^n{d}_i\ge 2n$ and give a sufficient and necessary condition for a multigraphic sequence $D$ with $d_n=2$ to be super edge-connected. Moreover, we show that a multigraphic sequence $D$ with $d_n\ge 3$ is always super edge-connected.