Extremality and Sharp Bounds for the k-edge-connectivity of Graphs

arXiv1901.06100MaRDI QIDQ6312657FDOQ6312657

Authors: Yuefang Sun, Xiaoyan Zhang, Zhao Zhang 

Publication date: 18 January 2019

Abstract: Boesch and Chen (SIAM J. Appl. Math., 1978) introduced the cut-version of the generalized edge-connectivity, named $k$-edge-connectivity. For any integer $k$ with $2leqkleqn$, the {em $k$-edge-connectivity} of a graph $G$, denoted by $lambd{a}_k(G)$, is defined as the smallest number of edges whose removal from $G$ produces a graph with at least $k$ components. In this paper, we first compute some exact values and sharp bounds for $lambd{a}_k(G)$ in terms of $n$ and $k$. We then discuss the relationships between $lambd{a}_k(G)$ and other generalized connectivities. An algorithm in $mathcalO(n^2)$ time will be provided such that we can get a sharp upper bound in terms of the maximum degree. Among our results, we also compute some exact values and sharp bounds for the function $f(n,k,t)$ which is defined as the minimum size of a connected graph $G$ with order $n$ and $lambd{a}_k(G)=t$.

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Connectivity (05C40)

This page was built for publication: Extremality and Sharp Bounds for the $k$-edge-connectivity of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6312657)