Increasing paths in random temporal graphs

06/20/2023
by   Nicolas Broutin, et al.
0

We consider random temporal graphs, a version of the classical Erdős–Rényi random graph G(n,p) where additionally, each edge has a distinct random time stamp, and connectivity is constrained to sequences of edges with increasing time stamps. We study the asymptotics for the distances in such graphs, mostly in the regime of interest where np is of order log n. We establish the first order asymptotics for the lengths of increasing paths: the lengths of the shortest and longest paths between typical vertices, the maxima of these lengths from a given vertex, as well as the maxima between any two vertices; this covers the (temporal) diameter.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset