Metraipolis › archive › dc_c10da43b2b0d

Average hitting times and recurrence structures II: Cartesian products of powers of cycles and regular graphs — arXiv:2608.11734

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.11734
License (as archived)
CC0-1.0
Archived
2026-10-19T05:47:43.015Z
SHA-256 of the archived text
214511efa63c46f4491b2d25f7ee83f4d2eed8658661fc0b123a7e712b6d450f
Stable URL of this page
https://metraipolis.com/documento/dc_c10da43b2b0d

How to cite

Average hitting times and recurrence structures II: Cartesian products of powers of cycles and regular graphs — arXiv:2608.11734 — arXiv (en), https://arxiv.org/abs/2608.11734 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c10da43b2b0d (Metraipolis archive dc_c10da43b2b0d, sha256 214511efa63c46f4491b2d25f7ee83f4d2eed8658661fc0b123a7e712b6d450f)
BibTeX
@misc{dcc10da43b2b0d,
  title = {Average hitting times and recurrence structures II: Cartesian products of powers of cycles and regular graphs — arXiv:2608.11734},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.11734},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c10da43b2b0d; sha256 214511efa63c46f4491b2d25f7ee83f4d2eed8658661fc0b123a7e712b6d450f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.11734. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In our previous work \cite{MiezakiTamura2026}, we clarified the second-order linear recurrence structures appearing in the average hitting times on the $k$-th power graph $C_N^k$ of the cycle graph. In this paper, for a connected $r$-regular graph $G$ on $m$ vertices, we investigate the average hitting times of the simple random walk on the Cartesian product graph $C_N^k \square G$. By using discrete Fourier analysis in the $C_N^k$ direction and the Laplacian spectral decomposition of $G$, we decompose the average hitting time into a component proportional to the average hitting time on $C_N^k$ and correction terms arising from the nonzero Laplacian eigenspaces of $G$. For each nonzero Laplacian eigenvalue, we introduce a Chebyshev-type polynomial, and when all of its roots are simple, we express the correction term as a finite Green-type sum. Furthermore, for two vertices having the same $G$-coordinate, we transform this expression into a second-order linear recurrence representation of the form $V_\ell V_{N-\ell}/V_N$. When $G$ is a walk-regular graph, the average hitting time between two vertices having the same $G$-coordinate depends only on the Laplacian eigenvalues of $G$ and their multiplicities. We also derive formulas for the number of spanning trees and the number of two-component spanning forests of $C_N^k \square G$, and give several explicit examples.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-13 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.11734 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T05:40:33.649Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-13?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).