The half-minimum-degree conjecture for restricted optimal pebbling

About 3 years old · traced to

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)≥12∣V(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.

References

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.