The dominating-set reformulation of the half-minimum-degree conjecture
The dominating-set reformulation of the half-minimum-degree conjecture
Let be a graph, with vertex set , minimum degree , open neighborhoods , and a set called dominating when it meets or is adjacent to every vertex of .
Dominating-set reformulation. If
then there are vertices and in such that
is a dominating set.
The source presents this as a reformulation of the preceding restricted-pebbling conjecture, using the fact that graphs with minimum degree at least half their order have diameter at most two and invoking earlier results. It is therefore not an independent mathematical claim, but a domination-theoretic equivalent formulation.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
László F. Papp, “Restricted optimal pebbling is NP-hard”, arXiv:2301.09867 (2023).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.