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, l ∈ K(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.
Schreiben Sie uns!