A Decomposition of the Hitting Time Index Using the Kirchhoff Index and an Asymmetry Term

Abstract

We study the hitting time index, a graph invariant defined in terms of expected hitting times of simple random walks on finite connected graphs, through its relation with the Kirchhoff index. Using the commute time identity and Tetali's formula, we decompose the hitting time index into a Kirchhoff-index term and a nonnegative asymmetry term expressed by degree-weighted effective resistance sums. We derive lower and upper bounds for the asymmetry term, together with their equality conditions, and obtain a lower bound for the hitting time index in terms of the range of the degree-weighted resistance sums. For trees, we obtain lower and upper bounds for the asymmetry term, with the upper bound expressed in terms of the Wiener index, and characterize the equality case in the lower bound. In particular, we show that among all trees of fixed order, the hitting time index is minimized uniquely by the star graph. Finally, we apply the decomposition to complete bipartite graphs, paths, and graphs obtained by conjoining complete graphs, and recover several known hitting-time formulas.

On the First Hitting Time Problems for Diffusion Processes: Local Time-Space Approach
Jerome Detemple, Yerkin Kitapbayev, Danila Shabalin
arXiv9 Oct 2026PreprintarXiv licenceFull textProbabilityarXiv
Budget-Constrained Graph Augmentation for Robust Network Design via Kirchhoff Index Minimization
Omkar Bhoite, V Sateeshkrishna Dhuli, Stefan Werner +1
arXiv24 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Hitting time for loose Hamilton cycles in the random hypergraph process
Jared León, Xizhi Liu
arXiv21 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Soltés problem for the Kirchhoff index of a graph
Kurt Klement Gottwald, Tomislav Došlić, Snježana Majstorović Ergotić
arXiv12 Sep 2026PreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
Hitting-Time Bounds for Asynchronous Q-Learning
Yang Peng
arXiv9 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{tamura2026decomposition,
  title = {{A Decomposition of the Hitting Time Index Using the Kirchhoff Index and an Asymmetry Term}},
  author = {Shunya Tamura and José Luis Palacios and Aleksandar Petojević},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.05663},
  eprint = {2610.05663},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.05663},
}

RIS

TY  - UNPB
TI  - A Decomposition of the Hitting Time Index Using the Kirchhoff Index and an Asymmetry Term
AU  - Shunya Tamura
AU  - José Luis Palacios
AU  - Aleksandar Petojević
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2610.05663
UR  - https://arxiv.org/abs/2610.05663
AB  - We study the hitting time index, a graph invariant defined in terms of expected hitting times of simple random walks on finite connected graphs, through its relation with the Kirchhoff index. Using the commute time identity and Tetali's formula, we decompose the hitting time index into a Kirchhoff-index term and a nonnegative asymmetry term expressed by degree-weighted effective resistance sums. We derive lower and upper bounds for the asymmetry term, together with their equality conditions, and obtain a lower bound for the hitting time index in terms of the range of the degree-weighted resistance sums. For trees, we obtain lower and upper bounds for the asymmetry term, with the upper bound expressed in terms of the Wiener index, and characterize the equality case in the lower bound. In particular, we show that among all trees of fixed order, the hitting time index is minimized uniquely by the star graph. Finally, we apply the decomposition to complete bipartite graphs, paths, and graphs obtained by conjoining complete graphs, and recover several known hitting-time formulas.
ER  -

Abstract

Related

Cite