The half-minimum-degree conjecture for restricted optimal pebbling
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.