Regular-graph reformulation of Boesch's maximum-girth conjecture
Regular-graph reformulation of Boesch's maximum-girth conjecture
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 is the length of its shortest cycle, and a -regular graph has every vertex of degree .
Regular Boesch conjecture. If an UMRG exists and has girth , then it has maximum girth among all -regular -graphs and, among the -regular -graphs with girth , it has the minimum number of -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 UMRG of girth .
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
Sign in to submit a solution.
No solutions have been posted yet.