Integrity and vertex neighbor integrity of some graphs

Abstract

The integrity \(I(G)\) of a noncomplete connected graph \(G\) is a measure of network vulnerability and is defined by \(I(G)=\min\limits_{S\subset V(G)}\{ |S|+m(G-S)\}\), where \(S\) and \(m(G-S)\) denote the subset of \(V\) and the order of the largest component of \(G-S\), respectively. The vertex neigbor integrity denoted as \(VNI(G)\) is the concept of the integrity of a connected graph \(G\) and is defined by \(VNI(G)=\min\limits_{S\subset V(G)}\{|S|+m(G-S)\}\), where \(S\) is any vertex subversion strategy of \(G\) and \(m(G-S)\) is the number of vertices in the largest component of \(G-S\). If a network is modelled as a graph, then the integrity number shows not only the difficulty to break down the network but also the damage that has been caused. This article includes several results on the integrity of the \(k\)-ary tree\( H_{n}^{k}\), the diamond-necklace \(N_{k}\), the diamond-chain \(L_{k}\) and the thorn graph of the cycle graph and the vertex neighbor integrity of the \(H_{n}^{2}\), \(H_{n}^{3}\).