Direkt zum Inhalt

Lexikon der Mathematik: Kantengraph

(engl. “linegraph“), zu einem Graphen G die Menge L(G), die als Eckenmenge die Kantenmenge K(G) besitzt, und in der k, lK(G) = E(L(G)) genau dann als Ecken adjazent sind, wenn sie als Kanten in G inzident sind.

Ist k = uv eine Kante des Graphen G, so gilt

dL(G)(k) = dG(u) + dG(v) − 2

für den Grad der Ecke k im Kantengraphen L(G).

Sind zwei Graphen isomorph, so sind natürlich auch ihre Kantengraphen isomorph. Im Jahre 1932 zeigte H.Whitney, daß auch die Umkehrung fast immer richtig ist.

Besitzen zwei zusammenhängende Graphen G und H isomorphe Kantengraphen, so sind auch G und H isomorph, es sei denn, der eine ist der vollständige Graph K3und der andere der vollständige bipartite Graph K1,3.

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