Edge Connectivity Problems in Telecommunication Networks

Abstract

If a communication network N with n stations has every station linked with at least [n/2] other stations, then the edge-connectivity of N equals its minimum degree. Also, in general, this limitation is stated to be the best possibility, as was proved by Chartrand in 1966. A more developed notion of edge-connectivity is introduced, which is called k-component order edge connectivity. It is the minimum number of edges required to be removed so that the order of each disconnected component is less than k.