Monotonicity of worst-case bottleneck values for degree-bounded spanning trees

From papers

Let vv be a root vertex with children {v1,,vk}\{v_1, \dots, v_k\}, where k2k \geq 2, the angles between children with respect to vv are at least 6060^{\circ}, and all children have radial distance 11. Let PP be the optimal bottleneck path that starts at vv and visits all children, and suppose that the children are placed to maximise the bottleneck length bb of PP. Likewise, let ww be a root vertex with children {w1,,wk+1}\{w_1, \dots, w_{k+1}\}, with pairwise angles at least 6060^{\circ} and radial distances equal to 11. Let PP' be the optimal bottleneck path that starts at ww and visits all children, and suppose that the children are placed to maximise the bottleneck length bb' of PP'. Monotonicity conjecture. Then bbb \geq b'. This asserts that adding a child cannot increase the worst-case bottleneck value. The claim is motivated by analytical and experimental point sets, but no proof or resolution is supplied here.

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

Patrick J. Andersen and Charl J. Ras, “Degree Bounded Bottleneck Spanning Trees in Three Dimensions”, arXiv:1812.11177 (2019).

Solutions 0

No solutions have been posted yet.