Rupture Degree of Mesh and Binary Trees

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) \geq 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.