Об асимптотике кратчайшего расстояния между крайними вершинами в обобщенном графе Барака-Эрдеша

Translated title of the contribution: On the asymptotics for the minimal distance between extreme vertices in a generalised Barak-Erdös graph

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

We consider a generalization of the Barak-Erdös random graph, which is a graph with an ordered set of vertices 0, 1, . . . n and with directed edges from i to j for i < j only, where each edge is present with a given probability p ∈ (0, 1). In our setting, probabilities p = pi,j depend on distances j - i and may tend to 0 as j - i → ∞. We study the asymptotics for the distribution of the minimal path length between 0 and n, when n becomes large.

Translated title of the contributionOn the asymptotics for the minimal distance between extreme vertices in a generalised Barak-Erdös graph
Original languageRussian
Pages (from-to)1556-1565
Number of pages10
JournalСибирские электронные математические известия
Volume15
DOIs
Publication statusPublished - 2018

Keywords

  • random graph
  • Barak - Erdos directed graph
  • minimal distance
  • boundary points
  • graph connectivity
  • first-passage percolation

OECD FOS+WOS

  • 1.01 MATHEMATICS

State classification of scientific and technological information

  • 27.45 Combinatorial analysis. Graph theory

Fingerprint

Dive into the research topics of 'On the asymptotics for the minimal distance between extreme vertices in a generalised Barak-Erdös graph'. Together they form a unique fingerprint.

Cite this