# zbMATH — the first resource for mathematics

A lower bound of the $$l$$-edge-connectivity and optimal graphs. (English) Zbl 1160.05039
Summary: For an integer $$l>1$$, the $$l$$-edge-connectivity of a graph $$G$$ with $$|V(G)| \geq l$$, denoted by $$\lambda_l(G)$$, is the smallest number of edges the removal of which 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 F.T. Boesch and S. Chen [”A generalization of line connectivity and optimally invulnerable graphs,” SIAM J. Math. 34, 657–665 (1978; Zbl 0386.05042)]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.

##### MSC:
 05C40 Connectivity 05C35 Extremal problems in graph theory
##### Keywords:
generalized edge connectivity; circulant graphs