Satz von Battle-Harary-Kodama

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Der Satz von Battle-Harary-Kodama ist ein mathematischer Lehrsatz, welcher dem Gebiet der Topologischen Graphentheorie angehört und auf eine Veröffentlichung der drei Mathematiker Joseph Battle, Frank Harary und Yukihiro Kodama aus dem Jahre 1962 zurückgeht. Er behandelt die Frage der Plättbarkeit von endlichen schlichten Graphen und der zugehörigen Komplementärgraphen und beruht auf einer Vermutung von John L. Selfridge. Im Jahre 1963 hat William Tutte einen vereinfachten Beweis des Satzes geliefert.

Formulierung des Satzes[Bearbeiten | Quelltext bearbeiten]

Der Satz lässt sich angeben wie folgt:[1]

(1) Ist ein endlicher schlichter Graph plättbar und hat er Knoten, so ist sein Komplementärgraph nicht plättbar.
(2) Die Zahl ist die kleinste natürliche Zahl mit dieser Eigenschaft.

Verwandter Satz[Bearbeiten | Quelltext bearbeiten]

Von Dennis P. Geller wurde ein verwandter Satz vorgelegt,[2] welcher die analoge Frage in Bezug auf die Eigenschaft der kreisartigen Plättkeit behandelt. Hier bezeichnet man einen endlichen schlichten Graphen als kreisartig plättbar, wenn eine ebene Darstellung in Form eines Streckengraphen besitzt, dessen Knoten sämtlich Randpunkte eines einzigen Landes der zugehörigen topologischen Landkarte sind.[3][4]

Der Satz von Geller lässt sich dann so formulieren:[2]

(1) Ist ein endlicher schlichter Graph kreisartig plättbar und hat er Knoten, so ist sein Komplementärgraph nicht kreisartig plättbar.
(2) Die Zahl ist die kleinste natürliche Zahl mit dieser Eigenschaft.

Quellen und Literatur[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise und Fußnoten[Bearbeiten | Quelltext bearbeiten]

  1. Frank Harary: Grapentheorie. 1974, S. 117–118
  2. a b Harary, op. cit., S. 118
  3. Harary, op. cit., S. 116
  4. In diese Begriffsfassung geht entscheidend der Satz von Wagner und Fáry ein.