The fair cake-cutting conjecture for uniformly most reliable hamiltonian graphs

Let FCGn,cFCG_{n,c} denote the fair cake-cutting graph with parameters nn and cc. A graph is uniformly most reliable for fixed order nn and size mm if its reliability polynomial is at least that of every competing graph for every edge-operational probability p[0,1]p\in[0,1]. Fair cake-cutting conjecture. If

n0(mod2c),n\equiv 0 \pmod{2c},

then FCGn,cFCG_{n,c} is a uniformly most reliable hamiltonian graph for m=n+cm=n+c. The case mn+4m\geq n+4 is described as largely open in the paper, with only some small cases known computationally; this conjecture proposes a family that is optimal under the stated divisibility condition.

Sources & referencesView supporting material

Primary source

Pol Llagostera, Nacho López and Carles Comas, “Network reliability in hamiltonian graphs”, arXiv:2005.02848 (2020).

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.