Quantitative Symmetry Breaking of Hitting Times at Cut Vertices

Abstract

For a simple random walk on a finite connected simple graph, we study how cut vertices create asymmetry of hitting times. Let c be a cut vertex with branches G_1, ..., G_s, and write m_i = |E(G_i)| and M = |E(G)|. Using the cut-vertex decomposition of hitting times, we derive, for every u in V(G_i) excluding c, the local-to-global ratio formula:

H_G(c,u) / H_G(u,c) = (M - m_i) / m_i + (M / m_i) * [H_Gi(c,u) / H_Gi(u,c)].

In particular,

H_G(c,u) / H_G(u,c) > (M - m_i) / m_i.

Consequently, at least s - 1 branches G_i satisfy H_G(c,u) > H_G(u,c) for every u in V(G_i) excluding c. On a branch having the minimum number of edges, the ratio is greater than s - 1. We show that this constant is asymptotically best possible.

These results imply that no finite connected simple graph with a cut vertex is highly symmetric and that K_2 is the only finite connected simple highly symmetric graph with a cut edge. This answers two questions posed by Palacios and Markowsky. We also combine the general reversibility identity for hitting times with the cut-vertex formulas to express the asymmetry between vertices lying in different branches explicitly in terms of local branch data.