für zwei disjunkte GraphenG 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 \begin{eqnarray}|E(G\times H)|=|E(G)\Vert E(H)|\end{eqnarray} und \begin{eqnarray}|K(G\times H)|=|E(G)\Vert K(H)|+|E(H)\Vert K(G)|.\end{eqnarray}Sind speziell G und Hbipartite Graphen, so kann man leicht nachweisen, daß dann auch das kartesische Produkt G × H bipartit ist. Im Fall, daß P und W zwei disjunkte Wege sind, nennt man P × W einen Gittergraphen. Nach obiger Bemerkung ist ein Gittergraph bipartit.

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\begin{eqnarray}\gamma (G)\gamma (H)\le \gamma (G\times H),\end{eqnarray}wobei γ(F) die Dominanzzahl eines beliebigen Graphen F bedeutet.

Bisher wurde Vizings Vermutung nur für spezielle Graphenklassen bewiesen, die allgemeine Lösung steht immer noch aus.