Long Paths and Cycles in Dynamical Graphs |
| |
Authors: | Tatyana S Turova |
| |
Institution: | (1) Department of Mathematical Statistics, University of Lund, Box 118, Lund, 22100, Sweden |
| |
Abstract: | We study the large-time dynamics of a Markov process whose states are finite directed 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 study the phase diagram. |
| |
Keywords: | branching processes dynamical random graphs phase transition randomly grown networks |
本文献已被 SpringerLink 等数据库收录! |
|