Direkt zum Inhalt

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 \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 H bipartite 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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos