Maximum Wiener index conjecture for directed grids

Let Gm,n=PmPnG_{m,n}=P_m\Box P_n be the Cartesian product of paths on m,n2m,n\geq 2 vertices. Let Dm,n{D}_{m,n} be the orientation of Gm,nG_{m,n} with all PmP_m-layers oriented up except the last PmP_m-layer, which is oriented down, and all PnP_n-layers oriented to the left except the first PnP_n-layer, which is oriented to the right. Write Wmax(Gm,n)W_{\rm \max}(G_{m,n}) for the maximum Wiener index over all orientations of Gm,nG_{m,n}, and W(Dm,n)W({D}_{m,n}) for the Wiener index of Dm,n{D}_{m,n}. Maximum Wiener index conjecture. For every m,n2m,n\geq 2, we have

Wmax(Gm,n)=W(Dm,n).W_{\rm \max}(G_{m,n})=W({D}_{m,n}).

The conjecture asserts that the natural generalization of the orientation known to maximize the Wiener index of the ladder graph Ln=P2PnL_n=P_2\Box P_n also maximizes the Wiener index for every directed grid. The ladder case was proved by Kraner Šumenjak et al.; the general case is presented as a conjecture.

Sources & referencesView supporting material

Primary source

Martin Knor and Riste Skrekovski, “On maximum Wiener index of directed grids”, arXiv:2201.11958 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.