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.

05C40 Connectivity
05C35 Extremal problems in graph theory