Finding Optimal Routings in Hamming Graphs

A routing R in a graph consists of a simple path p_uvfromu to v for each ordered pair of distinct vertices (u, v). We will call R optimal if all the paths p_uvare shortest paths and if edges of the graph occur equally often in the paths of R. In 1994, Solé gave a sufficient condition involving the automorphism group for a graph to have an optimal routing in this sense. Graphs which satisfy Solé’s condition are called orbital regular graphs. It is often difficult to determine whether or not a given graph is orbital regular. In this paper, we give a necessary and sufficient condition for a Hamming graph to be orbital regular with respect to a certain natural subgroup of automorphisms.