First-Return Walks on Vertex-Transitive Graphs
Abstract
For a connected vertex-transitive graph on N vertices with adjacency spectrum {(lambda_i, m_i)},
a closed walk based at a vertex is indecomposable (a "first return") if it revisits its base only
on the final step. This note records that the first-return counts follow from the spectrum alone
by a single rational operation: their generating function is 2 - 1/f(x), where
f(x) = (1/N) sum_i m_i/(1 - lambda_i x) is the closed-walk generating function. Each graph thus
yields an integer sequence obeying a linear recurrence whose order is the number of distinct
nonzero eigenvalues.
Specialising to the Hamming graphs H(k,q) - the Cayley graphs of (Z/q)^k with weight-one
generators - gives a two-parameter array with an explicit closed form covering hypercubes, rook's
graphs, and their q-ary generalisations. The q=2 case is the hypercube, and its row for fixed k
counts, under a dictionary made precise here, the irreducible theorems of the pure equivalential
calculus in k variables.
Three sequences produced by the construction were absent from the OEIS and have been submitted:
the 4-cube (A398262), the Petersen graph (A398309), and the icosahedron (A398310). All values were
verified three independent ways (spectral formula, adjacency-matrix powers, and brute-force word
enumeration); the verification code and b-files accompany the note.
The underlying tools - closed-walk counts as spectral moments, and the first-return/INVERT
decomposition - are classical; the contribution is the uniform statement, the Hamming closed form,
the recorded sequences, and the equivalential-calculus dictionary.
Cite it
Gonzalez, V. (2026). First-Return Walks on Vertex-Transitive Graphs. Zenodo. https://doi.org/10.5281/zenodo.21629398