Long Paths and Cycles in the Dynamical Graphs

Tatyana S. Turova


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

ISSN 1403-9338
Abstract:
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.