Bounds for scattering number and rupture degree of graphs with genus

Abstract For a given graph G = ( V , E ) , denote by m ( G ) and ω ( G ) the order of the largest component and the number of components of G , respectively. The scattering number of G is defined as s ( G ) = max { ω ( G − X ) − | X | : X ⊆ V , ω ( G − X ) > 1 } , and the rupture degree r ( G ) = max { ω ( G − X ) − | X | − m ( G − X ) : X ⊆ V ( G ) , ω ( G − X ) > 1 } . These two parameters are related to reliability and vulnerability of networks. In this paper, we present some new bounds on the scattering number and rupture degree of a graph G in terms of its connectivity κ ( G ) and genus γ ( G ). Furthermore, we give graphs to show these bounds are best possible.