From hitting times to the Wiener index of trees (Seminar DM)

Iz MaFiRaWiki

From hitting times to the Wiener index of trees

Stephan Wagner

Torek, 22. septembra 2015, od 10h do 12h, Plemljev seminar, Jadranska 19


Povzetek: We consider the simple random walk on a graph, which at each step moves to one of the neighbours chosen uniformly at random. The hitting time Hxy from a vertex x to a vertex y is the average time it takes a simple random walk starting at x to reach y. We present a surprising connection between the hitting time and the Wiener index (sum of all distances between pairs of vertices) of a tree, its ramifications and generalisations.

Glej tudi/See also

Seminar za diskretno matematiko

Osebna orodja