|
This article is cited in 2 scientific papers (total in 2 papers)
Probability theory and mathematical statistics
On the asymptotics for the minimal distance between extreme vertices in a generalised Barak–Erdös graph
P. I. Tesemnikov Novosibirsk State University,
Pirogova str., 1,
630090, Novosibirsk, Russia
Abstract:
We consider a generalization of the Barak–Erdös random graph, which is a graph with an ordered set of vertices $ \{ 0, 1, \ldots n \} $ and with directed edges from $ i $ to $ j $ for $ i < j $ only, where each edge is present with a given probability $ p \in (0, 1) $. In our setting, probabilities $ p=p_{i,j} $ depend on distances $ j - i $ and may tend to $ 0 $ as $ j - i \to \infty $. We study the asymptotics for the distribution of the minimal path length between $ 0 $ and $ n $, when $ n $ becomes large.
Keywords:
random graph, Barak–Erdös directed graph, minimal distance, boundary points, graph connectivity, first-passage percolation.
Received October 31, 2018, published December 4, 2018
Citation:
P. I. Tesemnikov, “On the asymptotics for the minimal distance between extreme vertices in a generalised Barak–Erdös graph”, Sib. Èlektron. Mat. Izv., 15 (2018), 1556–1565
Linking options:
https://www.mathnet.ru/eng/semr1014 https://www.mathnet.ru/eng/semr/v15/p1556
|
|