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 : \gamma(G,\Box,H) \ge \gamma(G)\gamma(H). , 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 . Examples A 4-cycle C4 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 C4 □ C4 is a four-dimensional hypercube graph; it has 16 vertices, and any single vertex can only dominate itself and four neighbor
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.
Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading