ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG and HH be undirected graphs. Write γ(G)\gamma(G) for the domination number of a graph, and let i(G)i(G) denote its independent domination number, the smallest size of an independent dominating set of GG. The Cartesian product G□HG\square H has vertex set V(G)×V(H)V(G)\times V(H). The independent domination conjecture.

i(G□H)≥min⁡{i(G)γ(H),γ(G)i(H)}.i(G\square H)\geq \min\{i(G)\gamma(H),\gamma(G)i(H)\}.

This is an analogue of Vizing's conjecture for independent domination and would imply Vizing's conjecture. The stronger product inequality i(G□H)≥i(G)i(H)i(G\square H)\geq i(G)i(H) is known to fail for some graphs, so this formulation avoids that obstruction; its resolution is not supplied in the source.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.