Vizing's conjecture

In graph theory, Vizing's conjecture concerns a relation between the domination number and the cartesian product of graphs. This conjecture was first stated by Template:Harvs, and states that, if Template:Math denotes the minimum number of vertices in a dominating set for the graph Template:Mvar, then

$\gamma (G◻H)\ge \gamma (G)\gamma (H).$

Template:Harvtxt conjectured a similar bound for the domination number of the tensor product of graphs; however, a counterexample was found by Template:Harvtxt. Since Vizing proposed his conjecture, many mathematicians have worked on it, with partial results described below. For a more detailed overview of these results, see Template:Harvtxt.

Examples

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

A 4-cycle Template:Math has domination number two: any single vertex only dominates itself and its two neighbors, but any pair of vertices dominates the whole graph. The product Template:Math is a four-dimensional hypercube graph; it has 16 vertices, and any single vertex can only dominate itself and four neighbors, so three vertices could only dominate 15 of the 16 vertices. Therefore, at least four vertices are required to dominate the entire graph, the bound given by Vizing's conjecture.

It is possible for the domination number of a product to be much larger than the bound given by Vizing's conjecture. For instance, for a star Template:Math, its domination number Template:Math is one: it is possible to dominate the entire star with a single vertex at its hub. Therefore, for the graph Template:Math formed as the product of two stars, Vizing's conjecture states only that the domination number should be at least Template:Math. However, the domination number of this graph is actually much higher. It has Template:Math vertices: Template:Math formed from the product of a leaf in both factors, Template:Math from the product of a leaf in one factor and the hub in the other factor, and one remaining vertex formed from the product of the two hubs. Each leaf-hub product vertex in Template:Mvar dominates exactly Template:Mvar of the leaf-leaf vertices, so Template:Mvar leaf-hub vertices are needed to dominate all of the leaf-leaf vertices. However, no leaf-hub vertex dominates any other such vertex, so even after Template:Mvar leaf-hub vertices are chosen to be included in the dominating set, there remain Template:Mvar more undominated leaf-hub vertices, which can be dominated by the single hub-hub vertex. Thus, the domination number of this graph is Template:Math 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. For instance, if Template:Mvar and Template:Mvar are both connected graphs, each having at least four vertices and having exactly twice as many total vertices as their domination numbers, then Template:Math. The graphs Template:Mvar and Template:Mvar with this property consist of the four-vertex cycle Template:Math together with the rooted products of a connected graph and a single edge.

Partial results

Clearly, the conjecture holds when either Template:Mvar or Template:Mvar has domination number one: for, the product contains an isomorphic copy of the other factor, dominating which requires at least Template:Math vertices.

Vizing's conjecture is also known to hold for cycles and for graphs with domination number two.

Template:Harvtxt proved that the domination number of the product is at least half as large as the conjectured bound, for all Template:Mvar and Template:Mvar.

Upper bounds

Template:Harvtxt observed that

$\gamma (G◻H)\le \min \{\gamma (G)|V(H)|,\gamma (H)|V(G)|\}.$

A dominating set meeting this bound may be formed as the cartesian product of a dominating set in one of G or H with the set of all vertices in the other graph.

References

• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.

External links

• Template:Mathworld