Linear domination conjecture for graph covers

Let FF be a graph, and let GG be a kk-fold cover of FF, meaning that each vertex of FF has kk vertices lying above it in the cover. Write 4γ(F)4\gamma(F) and 4γ(G)4\gamma(G) for the domination numbers of FF and GG, respectively.

Linear domination conjecture. There exists a constant c>0c>0 such that for every kk-fold cover GG of a graph FF,

γ(G)ckγ(F).\gamma(G) \geqslant c k\gamma(F).

The conjecture proposes a uniform linear lower bound for the domination number of a graph cover in terms of its fold and the domination number of the base graph. The supplied text gives motivating examples but no resolution, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Dickson Y. B. Annor, “Domination Parameters of Graph Covers”, arXiv:2502.14341 (2025).

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.