Random walks on graphs

F. Gobel, A.A. Jagers

Research output: Contribution to journalArticleAcademic

105 Citations (Scopus)
106 Downloads (Pure)


In this paper the following Markov chains are considered: the state space is the set of vertices of a connected graph, and for each vertex the transition is always to an adjacent vertex, such that each of the adjacent vertices has the same probability. Detailed results are given on the expectation of recurrence times, of first-entrance times, and of symmetrized first-entrance times (called commuting times). The problem of characterizing all connected graphs for which the commuting time is constant over all pairs of adjacent vertices is solved almost completely.
Original languageEnglish
Pages (from-to)311-336
JournalStochastic processes and their applications
Issue number4
Publication statusPublished - 1974


  • first entrance time
  • block of a graph
  • tree-wise join
  • Random walk
  • Balanced graph


Dive into the research topics of 'Random walks on graphs'. Together they form a unique fingerprint.

Cite this