The connected-graph bound for eternal connected domination

Let GG be a connected graph on nn vertices, let Δ(G)\Delta(G) denote its maximum degree, let θ(G)\theta(G) denote its clique covering number, and let γc(G)\gamma_c^{\infty}(G) denote its eternal connected domination number. The eternal connected domination conjecture. For every connected graph GG with

Δ(G)<n1,\Delta(G)<n-1,

one has

γc(G)>θ(G).\gamma_c^{\infty}(G)>\theta(G).

The source lists this among open problems in the other eternal-protection models.

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.