Component connectivity of generalized Petersen graphs

Abstract

Let G be a simple non-complete graph of order n. The r-component edge connectivity of G denoted as λ_r (G) is the minimum number of edges that must be removed from G in order to obtain a graph with (at least) r connected components. The concept of r-component edge connectivity generalizes that of edge connectivity by taking into account the number of components of the resulting graph. In this paper we establish bounds of the r component edge connectivity of an important family of interconnection network models, the generalized Petersen graphs GP(n, k) in which n and k are relatively prime integers.

Keywords:

• connectivity
• edge connectivity
• component connectivity
• generalized Petersen graphs

2010 AMS Subject Classifications:

• 05C40
• 05C38
• 05C75

Acknowledgements

The authors would like to thank the anonymous referees for their comments and suggestions to improve the paper.