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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page