Pure and Applied Mathematics Quarterly

Volume 11 (2015)

Number 3

Random walks on complete multipartite graphs

Pages: 393 – 402

DOI: https://dx.doi.org/10.4310/PAMQ.2015.v11.n3.a1

Authors

Xiao Chang (Department of Mathematics, University of Pittsburgh, Pennsylvania, U.S.A.)

Hao Xu (Department of Mathematics, University of Pittsburgh, Pennsylvania, U.S.A.)

Abstract

We apply Chung–Yau invariants to calculate the number of spanning trees of a complete multipartite graph. We also give explicit formulas for hitting times of random walks on a complete multipartite graph and prove that it has symmetric hitting times if and only it is vertex-transitive.

Keywords

random walk, Chung–Yau invariants, complete multipartite graph

2010 Mathematics Subject Classification

Primary 05C81. Secondary 05C50, 60G50.

Published 29 November 2016