Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 101.41001
Autor: Erdös, Paul; Gallai, Tibor
Title: On the minimal number of vertices representing the edges of a graph (In English)
Source: Publ. Math. Inst. Hung. Acad. Sci., Ser. A 6, 181-203 (1961).
Review: G sei ein schlingenfreier Graph ohne mehrfache Kante mit n Punkten und m Kanten; G kann auch isolierte Punkte enthalten. Die Punkte p1,...,pk bilden ein repräsentives System der Kanten von G, wenn jede Kante in mindestens einem der Punkte pi (1 \leq i \leq k) endet. \mu(G) = max k bezüglich aller repräsentiven Systeme von G. Es ist \mu(G) höchstens gleich dem harmonischen Mittel aus 1/2 n und m für m > 0. Gleichheit besteht nur dann, wenn alle Komponenten von G vollständige Graphen gleicher Punktzahl sind. Enthält G keine Kreise, so ist \mu (G) \leq 1/3 (n+m). Ist \mu (G') \leq p für alle Teilgraphen G' von G mit höchstens 2p+2 Punkten, dann ist \mu(G) \leq p. Es kann dabei 2p+2 nicht durch 2p+1 ersetzt werden, wie Beispiele zeigen. Enthält G mindestens 2p-h+3 Punkte ohne isolierte Punkte, wobei p hinreichend groß bezüglich h \geq 2 ist, ferner \mu(G') \leq p für jeden Teilgraphen G' und G mit höchstens p+h Kanten, dann ist \mu(G) \leq 2p-h.
In Verallgemeinerung des Problems treten an Stelle der Graphen, d.h. an Stelle zugeordneter Punktepaare k-tupel von Punkten und deren repräsentative Punktesysteme. Auch hier werden obere Schranken für die \mu(G) entsprechende Minimalzahl gegeben.
Reviewer: H.Künneth
Classif.: * 05C35 Extremal problems (graph theory)
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag