Vizing's conjecture

Vizing's conjecture is an important unsolved problem in the area of mathematics called graph theory. It deals with a special way of combining two graphs, known as the cartesian product of graphs. The conjecture was first suggested by a mathematician named Vadim G. Vizing.

The conjecture states a relationship between the domination number of a graph and the domination number of their cartesian product. If we think of a graph as a map of points (vertices) connected by lines (edges), the domination number tells us the smallest number of points needed so that every other point is either one of these chosen points or directly connected to one of them.

Vizing's conjecture claims that for any two graphs G and H, the domination number of their combined graph (G ◻ H) is at least as large as the product of the domination numbers of G and H individually. This means that combining graphs in this way doesn't make the dominating set smaller than expected; in fact, it might even require more points to dominate the combined graph.

Many mathematicians have studied this conjecture, finding partial results but not yet proving it fully. Solving Vizing's conjecture would give us deeper insights into how graphs behave when they are combined, and it remains an active area of research in graph theory.

Examples

A 4-cycle, written as (C_4), needs at least two vertices to cover, or "dominate," all its points. When you combine two of these cycles using a special operation, you get a graph with 16 points. In this new graph, you need at least four points to cover everyone, which matches what Vizing's conjecture predicts.

Sometimes, the number of points needed to cover a combined graph can be much higher than Vizing's conjecture suggests. For example, if you take two "star" shapes and combine them, the conjecture says you’d need at least one point to cover the whole thing. But in reality, you actually need many more points—specifically, (n + 1) points, where (n) is the number of points spreading out from the center in each star. This shows that the conjecture gives a lower limit, but actual numbers can be bigger.

There are also cases where the conjecture’s prediction is exactly right. If you have two connected graphs, each with at least four points and exactly half as many points needed to cover them as they have in total, then combining them will need exactly the product of those covering numbers. An example is using a 4-cycle together with certain other graphs.

Partial results

Vizing's conjecture has been shown to be true in some special cases. For example, it is clear when one of the graphs has only one vertex that needs to be watched over, because the combined graph will contain a copy of the other graph. The conjecture also holds for cycles and for graphs where watching over just two vertices is enough.

Researchers have also proven that for any two graphs, the number of vertices needed to watch over their combined graph is at least half of what the conjecture suggests it should be. This was shown by Clark and Suen in the year 2000.

Upper bounds

Vizing observed in 1968 that the domination number of the cartesian product of two graphs, ( G ) and ( H ), is less than or equal to the smaller of two values: the domination number of ( G ) multiplied by the number of vertices in ( H ), or the domination number of ( H ) multiplied by the number of vertices in ( G ).

This means that a dominating set for the product graph can be created by combining a dominating set from one graph with all the vertices from the other graph.