On maximum Wiener index of directed grids

Abstract

This paper is devoted to Wiener index of directed graphs, more precisely of directed grids. The grid G_m, n is the Cartesian product P_m□P_n of paths on m and n vertices, and in a particular case when m = 2, it is a called the ladder graph L_n. Kraner Šumenjak et al. in 2021 proved that the maximum Wiener index of a digraph, which is obtained by orienting the edges of L_n, is obtained when all layers isomorphic to one factor are directed paths directed in the same way except one (corresponding to an endvertex of the other factor) which is a directed path directed in the opposite way. Then they conjectured that the natural generalization of this orientation to G_m, n will attain the maximum Wiener index among all orientations of G_m, n. In this paper we disprove the conjecture by showing that a comb-like orientation of G_m, n has significiantly bigger Wiener index.