Long Paths and Cycles in the Dynamical Graphs

Tatyana S. Turova

Centre for Mathematical Sciences
Mathematical Statistics
Lund Institute of Technology,
Lund University,

ISSN 1403-9338
We study a large-time dynamics of a Markov process whose states are finite directed multi-graphs.
The number of the vertices is described by a supercritical branching process, and the edges follow a certain
mean-field dynamics determined by the rates of appending and deleting. We find sufficient conditions
under which asymptotically a.s. the order of the largest component is proportional to the order of the
graph. A lower bound for the length of the longest directed path in the graph is provided as well.
We derive an explicit formula for the limit as time goes to infinity, of the expected number of cycles of
     a given finite length. Finally, we discuss a phase diagram.