Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 137.43202
Autor: Erdös, Pál; Goodman, A.W.; Pósa, L.
Title: The representation of a graph by set intersections (In English)
Source: Can. J. Math. 18, 106-112 (1966).
Review: Eine Familie von Mengen S1,S2,... läßt sich auf natürliche Weise als Graph interpretieren, indem man jede Menge S\alpha als Punkt dieses Graphen auffaßt und vereinbart: (^*) Zwei Punkte sind genau dann durch eine Kante miteinander verbunden, wenn der Durchschnitt der beiden entsprechenden Mengen nicht leer ist. Es ist bekannt (vgl. E. Szpilrajn-Marczewski, Zbl 060.12508), daß auch umgekehrt zu jedem Graphen G eine Menge S und Untermengen S1,S2,... von S existieren, so daß eine eindeutige Zuordnung zwischen den Punkten x\alpha von G und den Untermengen S\alpha von S so möglich ist, daß (^*) gilt. Gegenstand der vorliegenden Untersuchungen ist die Minimalzahl der Elemente von S. Die Verff. beweisen:
Theorem 1. Ist G ein Graph mit n Punkten, dann gibt es eine Menge S mit [n2/4] Elementen und eine Familie von n Untermengen von S, so daß (^*) gilt. Weiterhin ist [n2/4] die kleinste solche Zahl.
Die Verff. zeigen, daß G sich als Summe von höchsten [n2/4] vollständigen Teilgraphen Gk angeben läßt [Kanten und Dreiecke (Theorem 2), diese können kantenfremd gewählt werden (Theorem 4)]. Zum Beweis von Theorem 1 wird jedem Punkt x\alpha von G die Menge S\alpha derjenigen Summanden Gk zugeordnet, die x\alpha enthalten. Interessant sind die Fragen der Verff. nach der minimalen Elementezahl von S bei Vorgabe auch der Kantenzahl von G sowie die Vermutung, daß sich jeder Graph mit n Punkten als Summe von höchstens n-1 Kreisen (auch eine einzelne Kante als Kreis gezählt) darstellen läßt. Ein Beweis von Theorem 1 für n \geq 4 mit der zusätzlichen Forderung, daß die n Untersuchungen von S paarweise verschieden sind, beschließt die anregende Arbeit.
Reviewer: W.Wessel (Berlin)
Classif.: * 05C35 Extremal problems (graph theory)
05C99 Graph theory
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag