On Oriented Diameter of Star Graphs
Satoshi Fujita · 2013
In this paper, we consider the problem of finding an orientation of star graphs to have the minimum oriented diameter. In contrast to undirected binary n-cube which connects 2nvertices with diameter n, an undirected star graph over n symbols (n-star) accommodates n! vertices with diameter 3(n-1)/2 . Our main contribution is the proposal of an upper bound on the minimum oriented diameter of n-star. The proposed upper bound is [5n/2]+2 for any n ≥ 3, which is a significant improvement of the upper bound 2n(n - 1) derived from a general inequality given by Chvatal and Thomassen.