Generalized edge-toughness

A communication network may be represented as a graph G=(V,E), where the nodes of the network (hosts, packet switches) and its communication links are modelled by the vertices and the edges of the graph respectively. The vulnerability of a communication network is defined as the measurement of the global strength of its underlying graph. A vulnerability index introduced by D. Gusfield (1983) of a graph G, called edge-toughness, and denoted by η(G), tells us that in order to split a graph G into k+ω(G), where ω(G) represents the number of connected components of G, we must then remove at least kη(G) edges from G, thus η(G) measures how tough it is to break up G. In this paper we propose a generalized edge-toughness index of a graph G, η_K(G). This index tells us how tough it is to break up the communication between the vertices of an arbitrary set K⊆V, |K|⩾2. Moreover we show that some of the properties of edge-toughness for the particular case K=V are extended to any arbitrary subset K⊆V