The Maximum Commute Time of Regular Graphs

@misc{huang2026maximum,
  title = {{The Maximum Commute Time of Regular Graphs}},
  author = {Jing Huang and Xuezhu Liao and Jiaxin Tang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.25800},
  eprint = {2610.25800},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.25800},
}

TY  - UNPB
TI  - The Maximum Commute Time of Regular Graphs
AU  - Jing Huang
AU  - Xuezhu Liao
AU  - Jiaxin Tang
PY  - 2026
DA  - 2026/10/19
PB  - arXiv
DO  - 10.48550/arxiv.2610.25800
UR  - https://arxiv.org/abs/2610.25800
AB  - For a connected simple regular graph G, let τ(G) be the maximum commute time for simple random walk, and let t_n be the maximum of τ(G) over all such graphs of order n. Aldous and Fill conjectured that t_n∼3n^2/2. We determine t_n exactly and classify all maximizers for every even n≥10 and every odd n≥15; both thresholds are best possible. The maximizers are cubic block chains joined by bridges at even orders and quartic block chains joined at cut vertices at odd orders. The exact formulas specify the linear corrections according to the order modulo four and five, respectively, and imply $ t_n\sim \begin{cases} \dfrac32 n^2, & n\text{ even},\\[1mm] n^2, & n\text{ odd}, \end{cases} \qquad n\to\infty. $ Thus the conjectured asymptotic formula holds along even orders but fails along odd orders. The proof combines unit-current potential orderings, cut-current inequalities, and sharp block resistance bounds, supplemented by finite computations in exact rational arithmetic.
ER  -