Paired Domination Integrity of Graphs.

The concept of vulnerability in a communication network plays an important role when there is a disruption in the network. There exist several graph parameters that measure the vulnerability of a communication network. Domination integrity is one of the vulnerability parameters that measure the performance of a communication network. In this paper, we introduce the concept of paired domination integrity of a graph as a new measure of graph vulnerability. Let G = (V,E) be a simple, connected graph. A set of vertices in a graph G, say S, is a paired dominating set if the following two conditions are satisfied: (i) every vertex of G has a neighbor in S and (ii) the subgraph induced by S contains a perfect matching. The paired domination integrity of G, denoted by PDI(G), is defined as PDI(G) = min{|S| + m(G − S) : S is a paired dominating set of G}, where m(G − S) is the order of the largest component in the induced subgraph of G − S. In this paper, we determine few bounds relating paired domination integrity with other graph parameters and the paired domination integrity of some classes of graphs. [ABSTRACT FROM AUTHOR]