Long paths and cycles in dynamical graphs

Research output: Contribution to journalArticle


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.


Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Probability Theory and Statistics


  • randomly grown networks, phase transition, branching processes, dynamical random graphs
Original languageEnglish
Pages (from-to)385-417
JournalJournal of Statistical Physics
Issue number1-2
Publication statusPublished - 2003
Publication categoryResearch