Monotonicity of worst-case bottleneck values for the (δ,k)(\delta,k)-PKRY algorithm

About 8 years old · traced to

For each mm, let SmS_m be a star with mm children rooted at its centre vertex, chosen to maximise the length of the longest edge in the tree produced by the (δ,k)(\delta,k)-PKRY algorithm, with every child at unit distance from the centre and no pair of children at distance less than 11. Define Sm+1S_{m+1} similarly with m+1m+1 children. Let bb and b′b' be the bottleneck values of the outputs of (δ,k)(\delta,k)-PKRY on SmS_m and Sm+1S_{m+1}, respectively. PKRY monotonicity conjecture. Then b≥b′b \geq b'. This is presented as a monotonicity property for worst-case arrangements, and the source describes it as a stronger version of an earlier conjecture; 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.