Quantitative Symmetry Breaking of Hitting Times at Cut Vertices
International Journal of Open Problems in Computer Science and Mathematics · 06.11.2026 · 19 (4) · 61-77
DOI: 10.15849/ijopcm.v19i4.107 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Open Problems in Computer Science and Mathematics, online erschienen am 06.11.2026. Verfasst von Shunya Tamura und 2 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
Tamura, S., Palacios, J. L., & Petojević, A. (2026). Quantitative Symmetry Breaking of Hitting Times at Cut Vertices. International Journal of Open Problems in Computer Science and Mathematics, 19(4), 61-77. https://doi.org/10.15849/ijopcm.v19i4.107
Vancouver
Tamura S, Palacios JL, Petojević A. Quantitative Symmetry Breaking of Hitting Times at Cut Vertices. International Journal of Open Problems in Computer Science and Mathematics. 2026;19(4):61-77. doi:10.15849/ijopcm.v19i4.107
BibTeX
@article{Tamura2026,
author = {Tamura, Shunya and Palacios, José Luis and Petojević, Aleksandar},
title = {Quantitative Symmetry Breaking of Hitting Times at Cut Vertices},
journal = {International Journal of Open Problems in Computer Science and Mathematics},
year = {2026},
volume = {19},
number = {4},
pages = {61--77},
doi = {10.15849/ijopcm.v19i4.107}
}
EUVIMED