Rupture Degree of Mesh and Binary Trees

Abstract

A well-designed interconnection network makes efficient use of scarce communication resources and is used in systems ranging from large supercomputers to small embedded systems on a chip. This paper deals with certain measures of vulnerability in interconnection networks. Let $G$ be a non-complete connected graph and for $S\subseteq V(G)$, let $\omega (G–S)$ and $m(G–S)$ denote the number of components and the order of the largest component in $G–S$, respectively. The vertex-integrity of $G$ is defined as

$$I(G)=\text{min}\{|S|+m(G–S):S\subseteq V(G)\}.$$

A set $S$ is called an $I$-set of $G$ if $I(G)=|S|+m(G–S)$. The rupture degree of $G$ is defined by

$$r(G)=\text{max}\{\omega (G–S)–|S|–m(G–S):S\subseteq V(G),\omega (G–S)\ge 2\}.$$

A set $S$ is called an $R$-set of $G$ if $r(G)=\omega (G–S)–|S|–m(G–S)$. In this paper, we compute the rupture degree of complete binary trees and a class of meshes. We also study the relationship between an $I$-set and an $R$-set and find an upper bound for the rupture degree of Hamiltonian graphs.