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

About 8 years old · traced to

Let vv be a root vertex with children {v1,…,vk}\{v_1, \dots, v_k\}, where k≥2k \geq 2, the angles between children with respect to vv are at least 60∘60^{\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 60∘60^{\circ} and radial distances equal to 11. Let P′P' 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 b′b' of P′P'. Monotonicity conjecture. Then b≥b′b \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.

References

Primary source

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

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.