Vizing's conjecture

This conjecture was first stated by Vadim G. Vizing (1968), and states that, if γ(G) denotes the minimum number of vertices in a dominating set for the graph G, then Gravier & Khelladi (1995) conjectured a similar bound for the domination number of the tensor product of graphs; however, a counterexample was found by Klavžar & Zmazek (1996).

Therefore, at least four vertices are required to dominate the entire graph, the bound given by Vizing's conjecture.

Therefore, for the graph G = K1,n □ K1,n formed as the product of two stars, Vizing's conjecture states only that the domination number should be at least 1 × 1 = 1.

Thus, the domination number of this graph is γ(K1,n □ K1,n) = n + 1 far higher than the trivial bound of one given by Vizing's conjecture.

There exist infinite families of graph products for which the bound of Vizing's conjecture is exactly met.

An optimal five-vertex dominating set in the product of two stars, K 1,4 □ K 1,4 . Examples such as this one show that, for some graph products, Vizing's conjecture can be far from tight.