The optimal-girth conjecture for Wiener-minimizing unicyclic graphs

Let D=(d1,d2,,dt1,dt,1,,1)D=(d_1,d_2,\dots,d_{t-1},d_t,1,\dots,1) be a degree sequence with dt2d_t\geq 2 and d22d_2\neq 2, and let GG be a unicyclic graph with degree sequence DD. Define

D=(d1,d2,,dt11,dt1,1,,1)D'=(d_1,d_2,\dots,d_{t-1}-1,d_t-1,1,\dots,1)

and let G(D)\mathcal{G}(D') be the greedy tree with degree sequence DD'. If h(G(D))h(\mathcal{G}(D')) is achieved by a unique leaf, set γ=2h(G(D))1\gamma^*=2h(\mathcal{G}(D'))-1; otherwise set γ=2h(G(D))\gamma^*=2h(\mathcal{G}(D')). Optimal-girth conjecture. The Wiener index of GG satisfies

W(G)minGu(D,γ),C(D,γ).W(G)\geq\min\\{\mathcal{G}_u(D,\gamma^*),\mathcal{C}(D,\gamma^*)\\}.

This conjecture proposes that, without fixing the girth, a Wiener-minimizing unicyclic graph is captured by one of the two indicated constructions at the girth determined by the height of the associated greedy tree. The supplied text does not state a resolution, so the conjecture is recorded as open.

Sources & referencesView supporting material

Primary source

Alewyn P. Burger and Valisoa R. M. Rakotonarivo, “On minimizing the Wiener index of unicyclic graphs with fixed girth and given degree sequence”, arXiv:2410.04903 (2024).

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.