Long Paths and Cycles in the Dynamical Graphs

Tatyana S. Turova

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.