A Survey on Complexity of Integrity Parameter

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 <em>G</em>, <em>I</em>(<em>G</em>), is defined to be min(| <em>S</em> | +<em>m</em>(<em>G</em> −<em> S</em>)) where <em>S</em> ⊂ <em>V</em> (<em>G</em>) and <em>m</em>(<em>G</em> − <em>S</em>) is the maximum order of the components of <em>G</em> − <em>S</em>. Similarly the edge-integrity of <em>G</em> is <em>I′</em>(<em>G</em>) := min(| <em>S</em> | +<em>m</em>(<em>G</em> − <em>S</em>)) where now <em>S</em> ⊆ <em>E</em>(<em>G</em>). Here and through the remaining sections, by an <em>I</em>-set (with respect to some prescribed graph <em>G</em>) we will mean a set <em>S</em> ⊂ <em>V</em> (<em>G</em>) for which <em>I</em>(<em>G</em>) =| <em>S</em> | +<em>m</em>(<em>G</em> − <em>S</em>). We define an<em> I′</em>-set similarly. <br />In this paper we show a lower bound on the edgeintegrity of graphs and present an algorithm for its computation.