TOPICS
Search

Vizing Conjecture

Let gamma(G) denote the domination number of a simple graph G. Then Vizing (1963) conjectured that

gamma(G)gamma(H)<=gamma(G×H),

where G×H is the graph product. While the full conjecture remains open, Clark and Suen (2000) have proved the looser result

gamma(G)gamma(H)<=2gamma(G×H).

See also

Domination Number, Vizing's Theorem

Explore with Wolfram|Alpha

References

Clark, W. E. and Suen, S. "An Inequality Related to Vizing's Conjecture." Electronic J. Combinatorics 7, No. 1, N4, 1-3, 2000. http://www.combinatorics.org/Volume_7/Abstracts/v7i1n4.html.Hartnell, B. and Rall, D. F. "Domination in Cartesian Products: Vizing's Conjecture." In Domination in Graphs--Advanced Topics (Ed. T. W. Haynes, S. T. Hedetniemi, and P. J. Slater). New York: Dekker, pp. 163-189, 1998.Vizing, V. G. "The Cartesian Product of Graphs." Vyčisl. Sistemy 9, 30-43, 1963.

Referenced on Wolfram|Alpha

Vizing Conjecture

Cite this as:

Weisstein, Eric W. "Vizing Conjecture." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/VizingConjecture.html

Subject classifications