On the reliability of generalized Petersen graphs


Ekinci G. , Gauci J. B.

DISCRETE APPLIED MATHEMATICS, vol.252, pp.2-9, 2019 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 252
  • Publication Date: 2019
  • Doi Number: 10.1016/j.dam.2017.02.002
  • Title of Journal : DISCRETE APPLIED MATHEMATICS
  • Page Numbers: pp.2-9
  • Keywords: Super-connectivity, Super-edge-connectivity, Generalized Petersen graph, Networks, EXTRACONNECTIVITY

Abstract

The super-connectivity (super-edge-connectivity) of a connected graph G is the minimum number of vertices (edges) that need to be deleted from Gin order to disconnect G without creating isolated vertices. We determine when the generalized Petersen graphs GP[n, k] are super-connected and super edge-connected, and show that their super-connectivity and their super-edge-connectivity are both equal to four when n is not an element of{2k, 3k}. These results partially answer a question by Harary (1983) and are of interest especially in the study of reliability and fault tolerance of interconnection networks, since the graphs in this class are good candidates for such networks. (C) 2017 Elsevier B.V. All rights reserved.