The diameter vulnerability of the generalized Petersen graph GP[tk,k]


BORUZANLI EKİNCİ G. , GAUCI J. B.

TURKISH JOURNAL OF MATHEMATICS, cilt.42, ss.2897-2915, 2018 (SCI İndekslerine Giren Dergi) identifier

  • Cilt numarası: 42 Konu: 6
  • Basım Tarihi: 2018
  • Doi Numarası: 10.3906/mat-1802-66
  • Dergi Adı: TURKISH JOURNAL OF MATHEMATICS
  • Sayfa Sayıları: ss.2897-2915

Özet

The diameter of a graph gives the length of the longest path among all the shortest paths between any two vertices of the graph, and the diameter vulnerability problem measures the change in the diameter upon the deletion of edges. In this paper we determine the diameter vulnerability of the generalized Petersen graph GP[tk,k], for integers t >= 2 and k >= 1, and show that (except for some small cases) the diameter remains unchanged upon the deletion of one edge. This work contributes towards a solution of the well-known (Delta, D, D', s)-problem, which attempts to find large graphs with maximum degree Delta and diameter D such that the subgraphs obtained by deleting any set of up to s edges have diameter at most D', preferably equal to D itself. In cases when the delay in communication across a network is directly related to the length of the paths between stations, network designers generally prefer to opt for graphs having the property of being resistant to drastic shocks upon the deletion of edges. This reliability property makes this class of graphs ideal to be used for modeling interconnection networks.