Characterization of factors guaranteeing well-dominated strong products
Statement
Let and 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 has vertex set , with adjacent to exactly when and . The graphs and are its factors.
Characterization conjecture. If is a well-dominated graph that is not trivially well-dominated, then there exists a well-dominated graph such that 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.