ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let Gm,n=Pm□PnG_{m,n}=P_m\Box P_n be the Cartesian product of paths on m,n≥2m,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,n≥2m,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=P2□PnL_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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.