Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 114.40004
Autor: Erdös, Pál
Title: Remarks on a paper of Pósa (In English)
Source: Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7, 227-229 (1962).
Review: Let G be a graph containing n vertices and k a natural number (1 \leq k < n/2). Denote by mk the maximum of {n-k \choose 2}+k2 and {n-[(n-1)/2] \choose 2}+[{(n-1) \over 2} ]2.
Theorem: If each vertex of G has a degree \geq k and G contains mk+1 edges, then G has a Hamilton line. The conclusion does not hold in general if G contains only mk edges.
The final part of the paper deals with conditions which assure the existence of an open Hamilton line; the conditions in question are resulting from combining the conditions of the theorem of L.Pósa (reviewed above, Zbl 114.40003) and of the first theorem.
Reviewer: A.Ádám
Classif.: * 05C45 Eulerian and Hamiltonian graphs
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag