Domination-packing conjecture for connected graphs

Let GG be a connected graph with at least two vertices. Write γ(G)\gamma(G) for its domination number, ρ(G)\rho(G) for its packing number, and Δ\Delta for its maximum degree.

Domination-packing conjecture. For every such graph,

γ(G)(Δ1)ρ(G)+1.\gamma(G) \leq (\Delta-1)\rho(G)+1.

The paper presents this as a stronger version of the previously stated conjecture, following the known bound γ(G)Δρ(G)\gamma(G)\leq\Delta\rho(G) for graphs without isolated vertices. The authors state that their techniques are still far from settling this conjecture.

Sources & referencesView supporting material

Primary source

Renzo Gómez and Juan Gutiérrez, “Domination and packing in graphs”, arXiv:2402.05088 (2024).

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.