The dominating-set reformulation of the half-minimum-degree conjecture

From papers

Let GG be a graph, with vertex set V(G)V(G), minimum degree δ(G)\delta(G), open neighborhoods N(u)N(u), and a set called dominating when it meets or is adjacent to every vertex of GG.

Dominating-set reformulation. If

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

then there are vertices uu and vv in GG such that

{u,v}(N(u)N(v))\{u,v\}\cup\left(N(u)\cap N(v)\right)

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

No solutions have been posted yet.