In this paper we consider specific directed graphs called "ladders". The vertices of the graph are randomly colored by green or red. Deleting the edges with at least one red endpoint one gets a random graph. We give a method for finding the exact asymptotics of the longest path of this random graph if the "height" of the ladder goes to infinity. The result is a generalization of a celebrated theorem of Erdos-Renyi. An example is given, illustrating the method.
Publié le : 1983-02-14
Classification:
Erdos-Renyi laws,
random graph,
longest runs,
large deviation,
60F15,
60F10,
05C20
@article{1176993670,
author = {Nemetz, T. and Kusolitsch, N.},
title = {A Method of Investigating the Longest Paths in Certain Random Graphs},
journal = {Ann. Probab.},
volume = {11},
number = {4},
year = {1983},
pages = { 217-221},
language = {en},
url = {http://dml.mathdoc.fr/item/1176993670}
}
Nemetz, T.; Kusolitsch, N. A Method of Investigating the Longest Paths in Certain Random Graphs. Ann. Probab., Tome 11 (1983) no. 4, pp. 217-221. http://gdmltest.u-ga.fr/item/1176993670/