### Abstract

Original language | English |
---|---|

Pages (from-to) | 311-336 |

Journal | Stochastic processes and their applications |

Volume | 2 |

Issue number | 4 |

DOIs | |

Publication status | Published - 1974 |

### Fingerprint

### Keywords

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

### Cite this

*Stochastic processes and their applications*,

*2*(4), 311-336. https://doi.org/10.1016/0304-4149(74)90001-5

}

*Stochastic processes and their applications*, vol. 2, no. 4, pp. 311-336. https://doi.org/10.1016/0304-4149(74)90001-5

**Random walks on graphs.** / Gobel, F.; Jagers, A.A.

Research output: Contribution to journal › Article › Academic

TY - JOUR

T1 - Random walks on graphs

AU - Gobel, F.

AU - Jagers, A.A.

PY - 1974

Y1 - 1974

N2 - 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.

AB - 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.

KW - first entrance time

KW - block of a graph

KW - tree-wise join

KW - Random walk

KW - Balanced graph

U2 - 10.1016/0304-4149(74)90001-5

DO - 10.1016/0304-4149(74)90001-5

M3 - Article

VL - 2

SP - 311

EP - 336

JO - Stochastic processes and their applications

JF - Stochastic processes and their applications

SN - 0304-4149

IS - 4

ER -