Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 090.39401
Autor: Erdös, Pál; Gallai, Tibor
Title: On maximal paths and circuits of graphs. (In English)
Source: Acta Math. Acad. Sci. Hung. 10, 337-356 (1959).
Review: Alle hier vorkommenden Graphen G haben n Knotenpunkte, \nu (G) sei die Kantenzahl von G. Ck sei der vollständige Graph mit k Punkten. Ist der Graph jedes Punktes \geq 1/2 (n-1) (n \geq 4), dann gibt es in G einen hamiltonschen Kreis und zwei beliebige Punkte aus G können durch eine offene hamiltonsche Linie verbunden werden. – Ist \nu(G) < 1/2 nl. bzw. > 1/2 (n-1)l, so enthält G einen Weg, bzw. Kreis mit mehr als l Kanten. Die Schranke ist genau im Fall n = q(l+1), bzw. n = q(l-1)+1, wie das Beispiel des Graphen zeigt, der Vereinigung von q Graphen Cl+1 ist, bzw. des zusammengesetzten Graphen, der q Glieder hat, von denen jedes ein Cl ist. – Ist n \geq (1/2 k+1)3 (k \geq 1), \nu(G) > nk-{k+1 \choose 2} = \phi(n,k), so enthält G einen Weg oder Kreis mit mehr als 2k Kanten. Daß die Schranke für \nu(G) genau ist, zeigt der Graph G^*k (2k \leq n), der zusammengesetzt ist aus einem Ck, einer aus n-k Punkten bestehenden Punktmenge Q und allen Kanten, die Punkte aus Q mit Punkten aus Ck verbinden. – Kanten heißen unabhängig, wenn sie paarweise keinen Punkt gemein haben. Ist k die Höchstzahl unabhängiger Kanten in G, so ist \nu(G) \leq max (\binom{2k+1}{2},\phi(n,k)). Das Gleichheitszeichen ist nur möglich, wenn G = G^*k oder G = C2k+1 \cup {pi}, wobei pi isolierte Punkte sind.
Reviewer: H.Künneth
Classif.: * 05C35 Extremal problems (graph theory)
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag