主題
Search

Vizing 猜想

設 gamma(G) 表示 簡單圖 G 的 支配數 G。然後 Vizing (1963) 猜想

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

其中 G×H 是 圖的乘積。雖然完整的猜想仍然是開放的，但 Clark 和 Suen (2000) 已經證明了較寬鬆的結果

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

參見

支配數, Vizing 定理

使用 探索

參考文獻

Clark, W. E. 和 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. 和 Rall, D. F. "Domination in Cartesian Products: Vizing's Conjecture." In 圖的支配——高階主題 (Ed. T. W. Haynes, S. T. Hedetniemi, 和 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.

在 上引用

Vizing 猜想

以此引用

Weisstein, Eric W. "Vizing 猜想。" 來自 Web 資源。 https://mathworld.tw/VizingConjecture.html

學科分類