Papex

Open problem · Mathematics · since 1968 · Open

Vizing’s conjecture

Is the domination number of the Cartesian product of two graphs always at least the product of their domination numbers?

Summary

Vadim Vizing stated the conjecture in 1968. It is known to hold for cycles and for graphs with domination number one or two, and Clark and Suen proved in 2000 that the product’s domination number is always at least half the conjectured bound. A similar bound proposed for the tensor product of graphs turned out to be false.

Source

Open, as listed by Wikipedia · Unsolved problems in mathematics. Checked 18 Nov 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Mathematics