Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 123.17004
Autor: Erdös, Pál
Title: On the structure of linear graphs. (In English)
Source: Israel J. Math. 1, 156-160 (1963).
Review: Es sei G(n; m) ein (nichtgerichteter) Graph mit n Knotenpunkten und m Kanten. Aus dem bekannten Satz von P.Turán folgt die spezielle Behauptung, daß jeder Graph G(n; [n2/4]+1) mindestens ein Dreieck enthält (n \geq 3). Der Verf. und G.A.Dirac haben unabhängig einen Satz gefunden, daß jeder Graph G(n; [n2/4]+1) für jede ganze Zahl k in < 4; n> einen Teilgraphen G(k; [k2/4]+1) enthält. In der vorliegenden Arbeit wird die Struktur der Graphen G(n; [n2/4]+1) und G(n; [tn3/2]) (für genügend großes t) ausführlich untersucht. Es werden z.B. die sogenannten vollständigen paaren Teilgraphen Ke (un, un) (mit einer weiteren Kante) und die im G(n; [n2/4]+1) bzw. G(n; [tn3/2]) liegenden Kreise betrachtet. Einige Vermutungen, die in dieser Arbeit offen geblieben sind, bezeichnet der Verf. als schwierig.
Reviewer: J.Sedlácek
Classif.: * 05C99 Graph theory
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag