Stephan Wagner: From hitting times to the Wiener index of trees

Datum objave: 16. 9. 2015
Seminar za diskretno matematiko
Torek, 22. 9. 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 H_{xy} 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.