The theory of regular graphs

Die vorliegende Arbeit ist bemerkenswert insofern sie mit Erfolg versucht, neuere Principien der Invariantentheorie, die sich an die Theorie der diophantischen Gleichungen anlehnen, auf rein anschaulichem Wege klarzulegen und weiterzuführen. Der Verf. ist dabei nach eigener Angabe durch einen regen Briefwechsel mit Hrn. Sylvester sehr gefördert worden. \textit{D. Hilbert} stützt sich bei seinem ersten ``Endlichkeitsbeweise [Math. Ann. 33, 223--226 (1889; JFM 20.0110.01)] auf einen Gordan'schen Satz, wonach sich bei gegebenem \(n\) eine endliche Anzahl von ``Grundproducten \[ (x_1-x_2)^\alpha (x_1-x_3)^\beta (x_2-x_3)^\gamma \dots (x_{n-1}-x_n)^\varepsilon \] bilden lässt, sodass alle anderen Producte derselben Form aus jenen durch Multiplication zusammensetzbar sind. Der Verf. stellt sich die Aufgabe, diese Grundproducte für verschiedene Werte von \(n\) wirklich zu bilden. Man repräsentire jedes \(x\) durch einen Punkt der Ebene, jeden Factor \(x_i-x_k\) durch eine beliebige Verbindungslinie zwischen \(x_i\) und \(x_k\); beispielsweise entspricht dann dem Producte \[ (x_1-x_2)^2(x_3-x_4)^2 (x_1-x_3)(x_2-x_4)(x_1-x_4)(x_2-x_3) \] ein Viereck mit seinen Diagonalen, von dem aber zwei Gegenseiten doppelt ausgezogen sind. Da die in Rede stehenden Ausdrücke in jedem \(x\) von gleichem Grade \(\alpha\) (nämlich dem Grade der entsprechenden Invariante) sind, so laufen in jedem Punkte unserer \(n\)-Ecke gleichviel Linien zusammen, daher die Bezeichnung: ``Regulärer Graph \(G_x^n\). Es kommt des weiteren wesentlich darauf an, ob ein Graph primitiv ist oder nicht; im letzteren Falle kann er durch Ueberlagerung mehrerer Graphs derselben Ordnung, aber von niedrigerem Grade entstanden gedacht werden. Die Hauptaufgabe ist demnach die Bestimmung aller primitiven Graphs. Hier zeigt sich nun ein merkwürdiger Unterschied, je nachdem der Grad gerade oder ungerade ist. Bei geradem Grade giebt es nur Grundfactoren ersten oder zweiten Grades. Bei ungeradem Grade dagegen können die Grundfactoren für ein genügend grosses \(n\) bis zu einem beliebigen Grade ansteigen; der einfachste ist hier vom dritten Grade für \(n = 10\). Zur Ableitung solcher Sätze bedarf es jedoch einer grossen Reihe von Hülfssätzen: es ist zu untersuchen, falls ein Graph auf verschiedene Weisen zerlegbar ist, wie diese Zerlegungen mit einander verknüpft sind, wie sie sich in einander überführen lassen, u. s. f. Eine besondere Bedeutung hat der Begriff zweier gepaarten Graphs (gerader Ordnung). Von diesen entsteht der eine aus dem anderen, indem zwei Linien \(ab\) und \(cd\) entfernt und dafür durch zwei andere \(ac\) und \(bd\) (resp. \(ad\) und \(bc\)) ersetzt werden. Die Natur der benutzten Methoden bringt es mit sich, dass eine weitere Auseinandersetzung hier zwecklos sein würde; es sei nochmals auf die geistreiche Arbeit selbst verwiesen.

Cited in

(51)

This page was built for publication: The theory of regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1531696)