Vulnerability in Networks - A Survey

Document Type: Research Paper


Department of Algorithms and Computation, Faculty of Engineering Science, School of Engineering, University of Tehran, Iran, and Department of Mathematics, UCLA, California, USA


The analysis of vulnerability in networks generally involves some questions
about how the underlying graph is connected. One is naturally interested
in studying the types of disruption in the network that maybe caused
by failures of certain links or nodes. In terms of a graph, the concept of
connectedness is used in different forms to study many of the measures
of vulnerability. When certain vertices or edges of a connected graph
are deleted, one wants to know whether the remaining graph is still
connected, and if so, what its vertex - or edge - connectivity is. If on the
other hand, the graph is disconnected, the determination of the number of
its components or their orders is useful. Our purpose here is to describe
and analyses the current status of the vulnerability measures, identify its
more interesting variants, and suggest a most suitable measure of