Some exact values for p(t,d)

Abstract

Let G = (V, E) be a graph. When a graph is used to model the linkage structure of communication networks, the diameter of a graph gives the length of longest path among all the shortest paths between any two vertices of the graph, F(t, d) denoted the minimum diameter of an altered graph obtained by adding t – extra edges to a graph with diameter d. Let P(t, d) denoted the minimum diameter of a graph obtained by adding t – extra edges to a path with diameter d. Knowing that F(t, d) = p(t, d). In this paper we prove that p(t, 3t) = 4, for t ≥ 4, p(t, d) = 4 where (t ≥ 4 and 3t +1 ≤ d ≤ 3t + 3) and show a construction to p(t, d) ≤ k + 3 where (3 ≤ t ≤ 5) and d = k(t + 1) + 8.

Subject Classification:

• 05
• 94C15

Keywords:

• Diameter
• Altered graph
• Edge addition