International Journal of Foundations of Computer Science · 1998 · 28 citations · 3 references
ComputingComputer ScienceMathematicsCombinatoricsComputer NetworksFault ToleranceGraph AlgorithmsGraph TheoryNetwork ConnectivityNetwork DiameterRoutingRouting AlgorithmsBroadcastDiameter Computation AlgorithmsGraph Theory In NetworksGraph-theoretic Network AnalysisInterconnection Graphs
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.
3