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, \ldots, d_n)\) with \(d_1 \geq d_2 \geq \ldots \geq d_n\) is called a multigraphic sequence if there is a multigraph with vertices \(v_1, v_2, \ldots, v_n\) such that \(d(v_i) = d_i\) for each \(i = 1, 2, \ldots, 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\limits_{i=1}^{n} d_i \geq 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 \geq 3\) is always super edge-connected.