The half-minimum-degree conjecture for restricted optimal pebbling

Let GG be a graph, with vertex set V(G)V(G), minimum degree δ(G)\delta(G), and pebbling numbers π(G)\pi^*(G) and π2(G)\pi_2^*(G) denoting its optimal and 22-restricted optimal pebbling numbers, respectively.

Half-minimum-degree conjecture. If

δ(G)12V(G),\delta(G)\geq \frac{1}{2}|V(G)|,

then

π2(G)=π(G).\pi_2^*(G)=\pi^*(G).

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 22-restricted pebble distribution of size 44 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

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.