On the Wiener index of orientations of graphs

The Wiener index of a strong digraph D is defined as the sum of the shortest path distances between all ordered pairs of vertices. This definition has been extended to digraphs that are not necessarily strong by defining the distance from a vertex a to a vertex b as 0 if there is no path from a to b in D. Knor et al. (2016) [9] considered (not necessarily strong) orientations of graphs with maximum Wiener index. The authors conjectured that for a given tree T, an orientation D of T of maximum Wiener index always contains a vertex v such that for every vertex u, there is either a (u,v)-path or a (v,u)-path in D. In this paper we disprove the conjecture. We also show that the problem of finding an orientation of maximum Wiener index of a given graph is NP-complete, thus answering a question by Knor et al. (2016) [8]. We briefly discuss the corresponding problem of finding an orientation of minimum Wiener index of a given graph, and show that the special case of deciding if a given graph on m edges has an orientation of Wiener index m can be solved in time quadratic in the order of the graph.