Reversible weighted graphs: symmetric hitting times and the weighted-cycle conjecture of Chang, Xu and Yau

An edge-weighted random walk on a finite connected graph moves from a vertex to a neighbor with probability proportional to the edge weight. The walk is always a reversible Markov chain in the detailed-balance sense, but symmetry of the hitting times themselves, $H(x,y)=H(y,x)$ for every vertex pair, is a rare structural property; graphs with it are called reversible in the sense of Georgakopoulos (2012). Chang, Xu and Yau (Pacific J. Math. 273 (2015) 241-255) reduced reversibility on weighted graphs to an implicit determinant criterion and conjectured an explicit classification for weighted cycles (their Conjecture 4.4): an odd cycle is reversible exactly when all edge weights are equal, an even cycle exactly when the weights alternate between two values. The sufficiency directions are known; the necessity directions are open, as is any structural characterization of reversible weighted graphs beyond cycles. Both necessity directions remain open as of 2026. The open core: prove that a reversible weighted cycle must carry the conjectured weight pattern (or refute this by an explicit weight assignment), and characterize the restrictions that reversibility imposes on edge weights for graph classes beyond cycles.

Background

Random walks on weighted graphs. Let $G$ be a finite connected undirected graph without loops in which each edge $xy$ carries a positive weight $w_{xy}$. The edge-weighted random walk on $G$ moves from a vertex $x$ to a neighbor $y$ with probability $w_{xy}/d_x$, where $d_x=\sum_{z\sim x}w_{xz}$ is the weighted degree of $x$. The hitting time $H(x,y)$ is the expected number of steps for the walk started at $x$ to first reach $y$. Every such walk is a reversible Markov chain in the classical sense: it satisfies detailed balance $\pi_x P(x\to y)=\pi_y P(y\to x)$ with respect to the stationary distribution $\pi_x=d_x/\operatorname{vol}(G)$, where $\operatorname{vol}(G)=\sum_x d_x$. This detailed balance says nothing about the symmetry of hitting times in their two arguments, and for a generic weighted graph $H(x,y)\ne H(y,x)$.

Graphs with symmetric hitting times. Following Georgakopoulos (2012), a graph is called reversible if $H(x,y)=H(y,x)$ for every pair of vertices - a much stronger property than detailed balance, introduced in the unweighted setting through questions of Aldous (1989) about return times on transitive graphs. Georgakopoulos observed that every walk-regular graph is reversible: a graph is walk-regular when the number of closed walks of length $k$ starting at a vertex $v$ is independent of $v$ for every $k$ (equivalently, the return probabilities of the walk do not depend on the starting vertex), and this forces the first-passage time between two vertices to have the same distribution in both directions. Every vertex-transitive graph (a graph whose automorphism group takes any vertex to any other, such as a cycle) is walk-regular, hence reversible. Georgakopoulos asked the converse-flavored question whether every reversible unweighted graph must be regular, or even walk-regular - suspected false, and still open.

Electrical interpretation and implicit criteria. Viewing a weighted graph as an electrical network whose edges are resistors of resistance $1/w_{xy}$, the effective resistance $R_{xy}$ between $x$ and $y$ is the voltage drop between them under a unit current flow. The classical commute-time identity $H(x,y)+H(y,x)=\operatorname{vol}(G) R_{xy}$ (Tetali 1991) shows that the sum of the two hitting times is always symmetric; the entire question is when the two terms split it evenly. Chang, Xu and Yau (2015), building on the discrete Green's function of Chung and Yau (2000) and on Xu and Yau (2013), expressed $H(x,y)$ on weighted graphs through enumerations of spanning trees and through two determinant-coefficient invariants $R(\cdot)$ and $Z(\cdot)$ of vertex-deleted graphs (the Chung-Yau invariants). Their Corollaries 2.9 and 2.10 give an exact implicit criterion: a weighted graph is reversible if and only if $Z(G-\{x\})$ - equivalently $\det B_{G-\{x\}}$ evaluated at $s=1$, for a matrix $B$ built from the weighted degrees - is independent of the deleted vertex $x$. This decides reversibility of any given weighted graph by computation, but gives no structural information about which weight patterns produce it.

The cycle conjecture. For the most basic non-tree family - the cycle $C_n$ with positive weights $w_1,\dots,w_n$ placed cyclically on the edges - the paper conjectures (Conjecture 4.4) an explicit classification: for odd $n$, the weighted $C_n$ is reversible if and only if all weights are equal; for even $n$, if and only if the weights alternate between two values, $w_1=w_3=\cdots=a$ and $w_2=w_4=\cdots=b$. The converse directions are known: constant weights reduce the walk to the simple random walk on a vertex-transitive graph, and the alternating case for even $n$ follows from the determinant criterion. The conjecture's open content is therefore the necessity of these patterns. Beyond cycles, the paper's stated open direction is precisely to study restrictions on edge weights for a reversible graph $G$; the authors' companion study (Chang and Xu 2017) develops the unweighted theory - determinant formulas for the asymmetry $H(x,y)-H(y,x)$, reversibility of special families, computational evidence toward Georgakopoulos's regularity question - but does not treat weighted graphs.

Problem Statement

Setup. Let $n\ge 3$ and let $C_n$ be the cycle on vertices $1,\dots,n$ with a positive weight $w_i$ on the edge $\{i,i+1\}$, indices taken modulo $n$. Let $H(x,y)$ denote the expected hitting time of the edge-weighted random walk on the weighted $C_n$.

Part 1 - the weighted-cycle conjecture (Conjecture 4.4 of Chang, Xu and Yau, necessity directions). Prove, or refute by an explicit counterexample: (i) if $n$ is odd and the weighted $C_n$ is reversible, that is $H(x,y)=H(y,x)$ for every vertex pair, then $w_1=\cdots=w_n$; (ii) if $n$ is even and the weighted $C_n$ is reversible, then $w_1=w_3=\cdots=w_{n-1}$ and $w_2=w_4=\cdots=w_n$. The converse directions are known: constant weights give the simple random walk on a vertex-transitive graph, and the alternating even case follows from the source paper's determinant criterion.

Part 2 - reversible weight assignments beyond cycles. Prove a theorem characterizing exactly which assignments of positive edge weights make a weighted graph reversible, for at least one infinite class of underlying graphs strictly containing all cycles - for example all unicyclic graphs (graphs containing exactly one cycle) or all graphs with at most two independent cycles (graphs whose cycle space has dimension at most two, i.e. cyclomatic number at most 2). The characterization must be structural: an explicit description of the reversible weight patterns, not a restatement of the implicit criterion that $Z(G-\{x\})$ is independent of $x$. The classification of reversible weighted cycles, in whichever form it takes after Part 1 is settled, must follow as a corollary.

The two parts jointly complete the source question of determining the restrictions that reversibility imposes on edge weights, of which the cycle conjecture is the concrete instance. The same source paper also leaves open a separate question - a criterion for finiteness of $H(x,y)$ on arbitrary locally finite infinite weighted graphs, where its Corollary 4.2 handles only trees; that infinite-graph question is not part of this problem's completion boundary.

References

1. Xiao Chang, Hao Xu, Shing-Tung Yau, Spanning trees and random walks on weighted graphs, Pacific Journal of Mathematics 273 (2015), no. 1, 241-255. DOI: 10.2140/pjm.2015.273.241, https://doi.org/10.2140/pjm.2015.273.241
2. Agelos Georgakopoulos, On walk-regular graphs and graphs with symmetric hitting times, preprint (2012). arXiv:1211.5689, https://arxiv.org/abs/1211.5689
3. Xiao Chang, Hao Xu, Chung-Yau invariants and graphs with symmetric hitting times, Journal of Graph Theory 85 (2017), 691-705. DOI: 10.1002/jgt.22099, https://doi.org/10.1002/jgt.22099
4. Agelos Georgakopoulos, Stephan Wagner, Hitting times, cover cost, and the Wiener index of a tree, Journal of Graph Theory 84 (2017), 311-326. DOI: 10.1002/jgt.22029, arXiv:1302.3212, https://doi.org/10.1002/jgt.22029
5. Hao Xu, Shing-Tung Yau, Discrete Green's functions and random walks on graphs, Journal of Combinatorial Theory, Series A 120 (2013), no. 2, 483-499. DOI: 10.1016/j.jcta.2012.10.002, https://doi.org/10.1016/j.jcta.2012.10.002
6. Fan Chung, S.-T. Yau, Discrete Green's functions, Journal of Combinatorial Theory, Series A 91 (2000), no. 1-2, 191-214. DOI: 10.1006/jcta.2000.3094, https://doi.org/10.1006/jcta.2000.3094
7. Prasad Tetali, Random walks and the effective resistance of networks, Journal of Theoretical Probability 4 (1991), no. 1, 101-109. DOI: 10.1007/bf01046996, https://doi.org/10.1007/bf01046996
8. David Aldous, Hitting times for random walks on vertex-transitive graphs, Mathematical Proceedings of the Cambridge Philosophical Society 106 (1989), 179-191. DOI: 10.1017/s0305004100068079, https://doi.org/10.1017/s0305004100068079
9. Greg Markowsky, Jose Luis Palacios, Symmetry in the Green's function for birth-death chains, Methodology and Computing in Applied Probability 21 (2019), no. 3, 841-851. DOI: 10.1007/s11009-017-9581-4, https://doi.org/10.1007/s11009-017-9581-4, https://arxiv.org/abs/1602.06001
10. Yuuho Tanaka, On the average hitting times of weighted Cayley graphs, preprint (2023). arXiv:2310.16571, https://arxiv.org/abs/2310.16571
11. Palle Jorgensen, Feng Tian, Infinite weighted graphs with bounded resistance metric, Mathematica Scandinavica 123 (2018), no. 1, 5-38. DOI: 10.7146/math.scand.a-106208, https://doi.org/10.7146/math.scand.a-106208
12. Xiaomin Zhu, Xiao-Dong Zhang, The Hitting Times of Random Walks on Bicyclic Graphs, Graphs and Combinatorics 37 (2021), 2365-2386. DOI: 10.1007/s00373-021-02360-3, https://doi.org/10.1007/s00373-021-02360-3