Long Paths and Cycles in the Dynamical Graphs
Tatyana S. Turova
Centre for Mathematical Sciences
Lund Institute of Technology,
We study a large-time dynamics of a Markov process whose states are finite
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.