Lexikon der Mathematik: kartesisches Produkt von Graphen
für zwei disjunkte Graphen G und H der Graph G × H mit folgenden Eigenschaften.
G × H besitzt als Eckenmenge das kartesische Produkt E(G) × E(H), und zwei Ecken (a, u) und (b, v) aus G × H sind genau dann adjazent, wenn a = b und u adjazent zu v oder u = v und a adjazent zu b ist. Es gilt
Im Zusammenhang mit dem kartesischen Produkt von Graphen hat V.G.Vizing 1963 folgende Vermutung publiziert.
Sind G und H zwei disjunkte Graphen, so gilt
Bisher wurde Vizings Vermutung nur für spezielle Graphenklassen bewiesen, die allgemeine Lösung steht immer noch aus.
Schreiben Sie uns!