Random Walks on Complete Multipartite Graphs

摘要

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.