On the classification of graphs. (Q559378)

Anknüpfend an eine Arbeit von \textit{R. M. Foster} (Geometrical circuits und elecrtical networks, Bell Telephone Technical Publications, Monograph B-653 = Transactions of the American Institute of electrical Engineers 51 (1932), 309-317; F. d. M. 58) gibt Verf. eine Klassifikation der Graphen nach der Nullität, genauer: er gibt ein Verfahren an, um zunächst besonders einfache Typen von nicht-separablen Graphen (für die Definition vgl. Verf., non separable und planar graphs, Transactions A. M. S. 34 (1932), 339-362; F. d. M. 58), die Basisgraphen (basic graphs), schrittweise nach wachsender Nullität zu konstruieren; daraus erhält man durch Anwendung eines einfachen Abänderungsprozesses (s. u. (4)) eine weitere Klasse spezieller Graphen von gleicher Nullität, die sogenannten Elementargraphen (elementary graphs), aus denen alle nichtseparablen Graphen vermittels der unten mit (1a) und (3) bezeichneten Abänderungen entstehen, deren Zusammenfassung zu nicht zusammenhängenden Graphen und Zusammensetzung nach (2) schließlich die separablen Graphen ergibt. Verf. betrachtet folgende Abäderunegen, deren jede die Nullität \(N\) des Graphen ungeändert läßt: {\parindent=8mm \begin{itemize}\item[(1a)]Ersetzen einer Kante \(ac\) durch zwei Kanten \(ab, bc\) unter Einführung eines neuen Knotenpunktes \(b\), und (1 b) den zu (1a) inversen Prozeß; \item[(2)]Identifikation eines Paares von Eckpunkten, die zu verschiedenen zusammenhängenden Bestandteilen des Graphen gehören, und der inverse Prozeß; \item[(3)]Abänderung der Zusammenheftung in einem trennenden Knotenpunktpaar nach folgender Vorschrift: Ist der Graph \(G\) aucs dem Teilgraphen \(H_1, H_2\) durch Identifikation von \(a_1\) mit \(a_2\), \(b_1\) mit \(b_2\) zusammengesetzt, während \(H_1\) und \(H_2\) sonst keinen Knotenpunkt gemeinsam haben, so identifiziere man statt dessen \(a_1\) mit \(b_2\) und \(a_2\) mit \(b_1\); \item[(4)]Tilgen einer Kante \(ab\) \((a\neq b)\) und Identifikation von \(a\) mit \(b\). \end{itemize}} Verf. nennt zwei Graphen \(G, G'\) isomorph (in früheren Arbeiten; kongruent oder homöomorph), wenn zwischen den Kanten und zwischen den Knotenpunkten von \(G\) und \(G'\) eine eineindeutige Zuordnung besteht, die die Inzidenzen erhält. Er gebraucht ferner die Bezeichnungen 1-isomorph, 2-isomorph, homöomorph, 1-homöo\-morph, 2-homöomorph, wenn \(G'\) durch Anwendung von (2) bzw. (2) und (3) bzw. (1a und b) bzw. (1a und b) und (2) bzw. (1a und b), (2) und (3) zu \(G\) isomorph wird. Elementargraph heißt ein nichtseparabler Graph, der zu keinem Graphen mit einer geringeren Anzahl von Kanten 2-homöomorph ist. Basisgraph heißt jeder kubische Elementargraph (d. h. ein solcher, bei dem jeder Knotenpunkt zu drei Kanten gehört), ferner der aus einer Kante mit identifizierten Endpunkten bestehende Graph. Für diesen letzten ist \(N=1\); der Basisgraph der Nullität 2 besteht aus zwei Knotenpunkten und drei sie verbindenden Kanten, der mit \(N=3\) ist der Kantenkomplex eines Tetraeders; bei höheren Nullitäten gibt es mehrere Basisgraphen (vgl. \textit{Foster}, a. a. O.) Bei 2-Homöomorphie bleibt die Nichtseparabilität erhalten, falls \(N>0\), Jeden zu einem Elementargraphen 2-homöomorphen Graphen kann man daraus durch Anwendung von (1a) und (3) erhalten, und zwar kann man dabei zuerst alle (1a), dann alle (3) ausführen, und - nach Definition des Elementargraphen - ist jeder nichtseparable Graph einem Elementargraphen 2-homöomorph (Erzeugung der nicht-separablen aus den Elementargraphen). 2-homöomorphe Elementargraphen sind also 2-isomorph. Bei \(N>0\) ist ein nichtseparabler Graph dann und nur dann ein Elementargraph, wenn er nach Herausnehmen von irgend zwei Kanten immer zusammenhängend bleibt. Anwendung von (4) führt daher einen Elementargraphen wieder in einen Elementargraphen über, falls die Nichtseparabilität erhalten bleibt. Basisgraphen mit \(N>2\) enthalten keine aus einer oder zwei Kanten bestehenden Kreise; sie sind dreifach zusammenhängend (d. h. werden durch einen und durch zwei Knotenpunkte nicht zerlegt), und daher sind - nach einem früheren Ergebnis des Verf. (Congruent graphs and connectivity of graphs, Amer. J. 54 (1932), 150-168; F. d. M. 58) - 2-homöomorphe Basisgraphen isomorph. Jeder nicht nur aus einer Kante bestehende Elementargraph ensteht aus einem Basisgraphen gleicher Nullität durch Anwendung von Operationen des Typus (4) (erzeugung der Elementargraphen aus Basisgraphen). Schließlich erhält man jeden Basisgraphen \(G\) mit \(N=k\) \((k>2)\) aus einem solchen \(G'\) mit \(N=k-1\) dadurch, dass\ man auf zwei verschiedene Kanten von \(G'\) (1a) anwendet und die beiden neuen Knotenpunkte durch eine Kante verbindet (Erzeugung der Basisgraphen verschiedener Nullitäten).