The additive lower bound for m-eternal vertex cover

Let G=(V,E)G=(V,E) be a connected graph, let HH be a subgraph of GG, and let G[VV(H)]G[V\setminus V(H)] be the subgraph induced by the vertices outside HH. Write δ()\delta(\cdot) for minimum degree and let τm\tau_{\mathrm{m}}^{\infty} denote the m-eternal vertex cover number. The additive eternal vertex cover conjecture. If

δ(H)2andδ(G[VV(H)])2,\delta(H)\geq2\quad\text{and}\quad\delta(G[V\setminus V(H)])\geq2,

then

τm(G)τm(H)+τm(G[VV(H)]).\tau_{\mathrm{m}}^{\infty}(G)\geq\tau_{\mathrm{m}}^{\infty}(H)+\tau_{\mathrm{m}}^{\infty}(G[V\setminus V(H)]).

The source presents this as an open conjecture in the eternal vertex-cover model.

Sources & referencesView supporting material

Primary source

William F. Klostermeyer and Christina M. Mynhardt, “Protecting a Graph with Mobile Guards”, arXiv:1407.5228 (2015).

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.