NETWORK PROPERTIES OF DOUBLE AND TRIPLE FIXED STEP GRAPHS
A.L. Liestman, Jaroslav Opatrný, Marisa Zaragozá · International Journal of Foundations of Computer Science · 1998
The network properties of double and triple fixed step graphs are considered. We determine that the broadcast times of double and triple fixed step graphs of diameter D are equal to D+2 and D+3, respectively. Some results on the embeddings of grids into these graphs with dilation 1 and 2 are given. For a triple fixed step graph we give a method to calculate the routing between any two vertices of the graph. Furthermore, we show that the diameter of the surviving route graph remains two for any set F of faults for |F|=5, which is optimum.