A Survey on Complexity of Integrity Parameter

Document Type: Research Paper

Author

University of Tehran, College of Engineering, Department of Engineering Science

Abstract

Many graph theoretical parameters have been used to describe the vulnerability of communication networks, including toughness, binding number, rate of disruption, neighbor-connectivity, integrity, mean integrity, edgeconnectivity vector, l-connectivity and tenacity. In this paper we discuss Integrity and its properties in vulnerability calculation. The integrity of a graph G, I(G), is defined to be min(| S | +m(G S)) where SV (G) and m(GS) is the maximum order of the components of GS. Similarly the edge-integrity of G is I′(G) := min(| S | +m(GS)) where now SE(G). Here and through the remaining sections, by an I-set (with respect to some prescribed graph G) we will mean a set SV (G) for which I(G) =| S | +m(GS). We define an I′-set similarly.
In this paper we show a lower bound on the edgeintegrity of graphs and present an algorithm for its computation.

Keywords