Random walks on graphs

F. Gobel; A.A. Jagers

doi:10.1016/0304-4149(74)90001-5

Random walks on graphs

F. Gobel, A.A. Jagers

University of Twente

Research output: Contribution to journal › Article › Academic

105 Citations (Scopus)

106 Downloads (Pure)

Abstract

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 language	English
Pages (from-to)	311-336
Journal	Stochastic processes and their applications
Volume	2
Issue number	4
DOIs	https://doi.org/10.1016/0304-4149(74)90001-5
Publication status	Published - 1974

Keywords

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

Access to Document

10.1016/0304-4149(74)90001-5Licence: Other

Gobel74randomFinal published version, 1.97 MBLicence: Other

Cite this

@article{f83d337883c54e62adb02b20285a99bd,

title = "Random walks on graphs",

abstract = "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.",

keywords = "first entrance time, block of a graph, tree-wise join, Random walk, Balanced graph",

author = "F. Gobel and A.A. Jagers",

year = "1974",

doi = "10.1016/0304-4149(74)90001-5",

language = "English",

volume = "2",

pages = "311--336",

journal = "Stochastic processes and their applications",

issn = "0304-4149",

publisher = "Elsevier",

number = "4",

}

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 -

Random walks on graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this