Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 203.56902
Autor: Erdös, Paul; Rényi, Alfréd
Title: On the existence of a factor of degree one of a connected random graph (In English)
Source: Acta Math. Acad. Sci. Hung. 17, 359-368 (1966).
Review: Die Arbeit schließt sich an die Artikel der Verff. [ibid. 12, 261-267 (1961; Zbl 103.16301); Publ. Math. Inst. Hung. Acad. Sci., Ser. A 8, 455-461 (1963; Zbl 133.26002)] an. Es wird der zufällige nichtorientierte Graph \Gamman,N mit n Knotenpunkten und N Kanten (ohne Schleifen und Parallelkanten) untersucht, in dem jede beliebige Wahl von N Kanten aus 1/2 n(n-1) möglichen Kanten die gleiche Wahrscheinlichkeit hat. Pn,N(F) bedeutet die Wahrscheinlichkeit dafür, daß im Graphen \Gamman,N ein Faktor ersten Grades (volle Paarkombination) existiert. Hauptresultat: ist n gerade, N = 1/2 n ln n+n · \omega(n), wo limn ––> +oo \omega(n) = +oo, so gilt limn ––> +ooPn,N(F) = 1.
Reviewer: K.Zaretskij (R.Z.Mat.1967, No.9B 199)
Classif.: * 05C70 Factorization, etc.
05C80 Random graphs
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag