The Oriented Diameter Of Hamming Graphs

Let S be a set of n elements and m a positive integer. The Hamming graph H(m,n) has vertex set Sm,the set of ordered m-tuples of elements of S, or sequences of length m from S. Two vertices are adjacent if they differ in precisely one coordinate. By the definition, it can be easily seen that H(m,2) is isomorphic to the hypercube Qm. For a bridgeless connected undirected graph G, the oriented diameter of it is the smallest diameter among all the diameters of strongly connected orientations of G. The oriented diameter of Qm has been solved completely. In this thesis, we study the oriented diameter of Hamming graphs by presenting the upper bound as follows:The oriented number p(G) of a graph G is defined to be the difference between the oriented diameter and the diameter of it, that is, p(G)=(?)(G)-d(G), where d(G) stands for the diameter of G. Since d(H(m,n))=m, we obtain that...