Regular-graph reformulation of Boesch's maximum-girth conjecture

At least 3 years old · documented by

Let a uniformly most reliable graph (UMRG) be a graph with the highest all-terminal reliability among graphs having the same order and size, for every edge-failure probability. For a graph, the girth gg is the length of its shortest cycle, and a kk-regular graph has every vertex of degree kk.

Regular Boesch conjecture. If an (n,kn/2)(n,kn/2) UMRG exists and has girth gg, then it has maximum girth among all kk-regular (n,kn/2)(n,kn/2)-graphs and, among the kk-regular (n,kn/2)(n,kn/2)-graphs with girth gg, it has the minimum number of gg-cycles.

This is presented as a reformulation of Boesch's maximum-girth conjecture. The supplied text does not give a separate resolution of this reformulation; the broader maximum-girth claim is nevertheless refuted by the reported 4-regular (9,18)(9,18) UMRG of girth 33.

References

Primary source

Nicole Rosenstock and Eduardo A. Canale, “Counterexample to a Boesch's Conjecture”, arXiv:2212.03912 (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.