This article is cited 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.

UDC: 519.175.4

MSC: 05C80

Received October 31, 2018, published December 4, 2018

DOI: 10.33048/semi.2018.15.129

Bibliographic databases:

•