Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Vizing's conjecture
Summary
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 , and states that, if γ(G) denotes the minimum number of vertices in a dominating set for the graph G, then
conjectured a similar bound for the domination number of the tensor product of graphs; however, a counterexample was found by . 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 .
A 4-cycle C_4 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 C_4 □ C_4 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 K_1,n, its domination number γ(K_1,n) is one: it is possible to dominate the entire star with a single vertex at its hub. Therefore, for the graph G = K_1,n □ K_1,n formed as the product of two stars, Vizing's conjecture states only that the domination number should be at least 1 × 1 = 1. However, the domination number of this graph is actually much higher. It has n2 + 2n + 1 vertices: n2 formed from the product of a leaf in both factors, 2n 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 G dominates exactly n of the leaf-leaf vertices, so n leaf-hub vertices are needed to dominate all of the leaf-leaf vertices.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.