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

Abstract

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\geq 2$ and $k\geq 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.