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

From papers

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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Nicole Rosenstock and Eduardo A. Canale, “Counterexample to a Boesch's Conjecture”, arXiv:2212.03912 (2022).

Solutions 0

No solutions have been posted yet.