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 14039338

Abstract:

We study a largetime dynamics of a Markov process whose states are finite
directed multigraphs.

The number of the vertices is described by a supercritical branching process,
and the edges follow a certain

meanfield 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.
