A Lower Bound of the $l$-Edge-Connectivity and Optimal Graphs

Abstract

For an integer $l>1$, the $l$-edge-connectivity of a graph $G$ with $|V(G)|\ge l$, denoted by ${\lambda }_l(G)$, is the smallest number of edges whose removal results in a graph with $l$ components. In this paper, we study lower bounds of ${\lambda }_l(G)$ and optimal graphs that reach the lower bounds. Former results by Boesch and Chen are extended.

We also present in this paper an optimal model of interconnection network $G$ with a given ${\lambda }_l(G)$ such that ${\lambda }_2(G)$ is maximized while $|E(G)|$ is minimized.