Bollobás–Scott weighted long-cycle conjecture for Eulerian digraphs

A digraph is a directed graph; it is Eulerian when it is strongly connected and every vertex has equal in-degree and out-degree. For a digraph GG, let A(G)A(G) denote its arc set, let w:A(G)R0w:A(G)\to\mathbb{R}_{\geq 0} be a weight function, and write w(G)w(G) for the total weight of its arcs. Bollobás–Scott's weighted long-cycle conjecture. Every nn-vertex Eulerian digraph GG with a weight function w:A(G)R0w:A(G)\to\mathbb{R}_{\geq 0} has a directed cycle of length at least

cw(G)nc\cdot\frac{w(G)}{n}

for some universal constant c>0c>0. This conjecture proposes a linear lower bound in the average arc weight for the length of a directed cycle and generalizes unweighted long-cycle questions for Eulerian digraphs.

Sources & referencesView supporting material

Primary source

Jiangdong Ai, Gregory Gutin, Fankang He and Anders Yeo, “Note on Long Directed Cycles in Eulerian Digraphs”, arXiv:2510.26426 (2025).

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.