DIAMETER VULNERABILITY OF DIRECTED CYCLES AND DIRECTED TORI
Xiao-Yan Ma, Xiaohui Huang, Zhao Zhang · Discrete Mathematics Algorithms and Applications · 2012
The diameter of a graph is important for the network as it measures the maximum communication delay between any pair of processors. In this paper, we study the diameter vulnerability of the directed cycle [Formula: see text] and the directed torus [Formula: see text] with respect to arc addition, that is, what is the minimum number of arcs the addition of which reduces the diameter by at least k.