ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG and HH be nontrivial graphs. A graph is trivially well-dominated if its closed neighborhoods form a clique partition of its vertex set. A graph is well-dominated if all its minimal dominating sets have the same cardinality. The strong product G⊠HG\boxtimes H has vertex set V(G)×V(H)V(G)\times V(H), with (u1,v1)(u_1,v_1) adjacent to (u2,v2)(u_2,v_2) exactly when u2∈NG[u1]u_2\in N_G[u_1] and v2∈NH[v1]v_2\in N_H[v_1]. The graphs GG and HH are its factors.

Characterization conjecture. If GG is a well-dominated graph that is not trivially well-dominated, then there exists a well-dominated graph HH such that G⊠HG\boxtimes H is not well-dominated.

The preceding theorem shows that a trivially well-dominated factor guarantees that the strong product with every well-dominated graph is well-dominated. This conjecture asserts that these are precisely the factors with that universal property.

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.