Narrow Results

In a communication network, the vulnerability measures are essential to guide the designer in choosing an appropriate topology. They measure the stability of the network to disruption of operation after the failure of certain stations or communication links. If a station or operative is captured in a spy network, then the adjacent stations will be betrayed and are therefore useless in the whole network. In this sense, Margaret B. Cozzens and Shu-Shih Y. Wu modeled a spy network as a graph and then defined the neighbor integrity of a graph to obtain the vulnerability of a spy network [10]. The neighbor integrity of a graph G, is defined to be , where S is any vertex subversion strategy of G and c(G/S) is the maximum order of the components of G/S. In this paper, we investigate the transformation graphs G^-+-, G^+--, G^++-, G^---, G^+-+, G^-++, G^--+ and G⁺⁺⁺ of a graph G, and determine their neighbor integrity.

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\text{ 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.

For a given graph G = (V, E), its integrity is defined as I(G) = min_X⊂V {|X|+m(G−X)}, where m(G−X) denote the order of the largest component of G−X. In [9], authors discuss the minimum integrity of tree with given order and the maximum degree. In this paper, we point that the result in [9] is flawed and by elementary method characterize the structure of the minimum integrity tree and thus correct Theorem 4.1 in [9]. Finally, we give the construction method of this kind of extremal graph.

The integrity of a graph $G$ is defined as the minimum value of $\left|S\right|+m(G-S)$ taken over all $S\subseteq V(G)$, where $m(H)$ denotes the maximum cardinality of a component of graph $H$. In this paper, we investigate bounds on the maximum and minimum values of the weighted version of this parameter. We also consider the same question for the related parameter vertex-neighbor-integrity.