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. | Turk J Math (2018) 42: 2897 – 2915 © TÜBİTAK doi: Turkish Journal of Mathematics Research Article The diameter vulnerability of the generalized Petersen graph GP [tk, k] Gülnaz BORUZANLI EKİNCİ1 ,, John Baptist GAUCI2∗, Department of Mathematics, Faculty of Science, Ege University, İzmir, Turkey 2 Department of Mathematics, Faculty of Science, University of Malta, Msida, Malta 1 Received: • Accepted/Published Online: • Final Version: 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 ≥ 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 (∆, D, D′ , s) -problem, which attempts to find large graphs with maximum degree ∆ 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. Key words: Diameter vulnerability, fault tolerance, generalized Petersen graph, paths 1. Introduction and definitions Let G be an undirected simple graph, where V (G) and E(G) denote the set of vertices and the set of edges, respectively. For two vertices x1 , x2 ∈ V (G) , x1 and x2 are adjacent if there is an edge e = x1 x2 .
