The half-minimum-degree conjecture for restricted optimal pebbling
Let be a graph, with vertex set , minimum degree , and pebbling numbers and denoting its optimal and -restricted optimal pebbling numbers, respectively.
Half-minimum-degree conjecture. If
then
Graphs whose minimum degree is at least half their order have diameter at most two, so the conjecture reduces to proving the existence of a solvable -restricted pebble distribution of size for every such graph. The source states that this threshold was not determined and presents this claim as the next conjecture.
References
Primary source
László F. Papp, “Restricted optimal pebbling is NP-hard”, arXiv:2301.09867 (2023).
Progress summary
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.