Direkt zum Inhalt

Lexikon der Mathematik: Potenz eines Graphen

bezeichnet mit Gp, besteht aus der Eckenmenge E(G) eines Graphen G, mit der Vorschrift, daß zwei Ecken u und v genau dann adjazent in Gp sind, wenn für den Abstand dG(u, v) ≤ p gilt, wobei p eine natürliche Zahl bedeutet. Man spricht dann genauer auch von der p-ten Potenz des Graphen G.

Im Jahre 1974 bemerkte D.P. Sumner, daß G2 ein perfektes Matching hat, falls G ein gerader zusammenhängender Graph ist. Entsteht der Baum T aus dem vollständigen bipartiten Graphen K1,3 durch zweifaches unterteilen jeder Kante, so überzeugt man sich leicht davon, daß in T2 kein Hamiltonscher Kreis existiert. Im Jahre 1960 zeigte M. Sekanina, daß sich die Situation ändert, wenn man anstelle von T2 die dritte Potenz eines Graphen betrachtet:

Ist G ein zusammenhängender Graph mit mindestens 3 Ecken, so ist G3Hamilton-zusammenhängend.

Mittels eines schwierigen Beweises konnte H. Fleischner 1974 dann folgende Vermutung von C.St.J.A. Nash-Williams und M.D. Plummer bestätigen.

Ist G ein Graph ohne Artikulation mit mindestens drei Ecken, so ist G2Hamiltonsch.

Als Anwendung dieses Satzes von Fleischner haben verschiedene Autoren im gleichen Jahr nachweisen können, daß G2 sogar Hamilton-zusammenhängend ist, falls G keine Artikulation besitzt. Darüber hinaus hat L. Nebeský 1980 bemerkt, daß man aus Fleischners Satz leicht das nächste Resultat folgern kann.

Ist G ein beliebiger Graph mit mindestens drei Ecken, so ist G2oder (\(\bar{G}\))2Hamiltonsch, wobei \(\bar{G}\)der Komplementärgraph von G ist.

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

Partnerinhalte