Number of spanning trees in a wheel graph with two identified vertices via hitting times

Shunya Tamura; Yuuho Tanaka

arxiv: 2502.01965 · v1 · submitted 2025-02-04 · 🧮 math.CO

Number of spanning trees in a wheel graph with two identified vertices via hitting times

Shunya Tamura , Yuuho Tanaka This is my paper

Pith reviewed 2026-05-23 04:42 UTC · model grok-4.3

classification 🧮 math.CO

keywords wheel graphspanning treeshitting timesFibonacci numbersLucas numberseffective resistancerandom walks on graphsgraph enumeration

0 comments

The pith

The number of spanning trees in a wheel graph with two identified vertices is obtained exactly from average hitting times expressed in Fibonacci and Lucas numbers.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper derives an exact combinatorial formula for average hitting times between vertices in the wheel graph W_{N+1}. These times take the form of Fibonacci numbers when the number of rim vertices is odd and Lucas numbers when even. The authors then substitute the hitting-time expression into the general effective-resistance formula to count the spanning trees of the graph formed by identifying any two vertices. A reader would care because spanning-tree enumeration is a standard combinatorial problem, and the derivation supplies a closed-form route for this symmetric family without direct counting.

Core claim

The paper establishes an exact formula for the average hitting times in the wheel graph W_{N+1} via a combinatorial approach. The formula expresses these times using Fibonacci numbers when the number of surrounding vertices is odd and Lucas numbers when even. Substituting this formula into the general expression for effective resistance then yields the number of spanning trees in the graph obtained by identifying two vertices.

What carries the argument

The combinatorial derivation of average hitting times that reduces the wheel-graph random-walk problem to recurrence relations solved by Fibonacci and Lucas sequences, followed by substitution into the effective-resistance identity.

If this is right

A closed-form count of spanning trees exists for every wheel graph with any two vertices identified.
Effective resistance between the identified pair equals the hitting-time difference scaled by the number of edges.
The same hitting-time recurrences supply explicit resistance values between any pair of vertices on the wheel.
The Fibonacci-Lucas distinction tracks the parity of the rim size and produces integer counts without approximation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same substitution technique could be tried on other vertex-transitive graphs whose hitting times admit simple recurrences.
The appearance of Fibonacci and Lucas sequences points to an underlying path-counting or tiling interpretation inside the wheel.
One could check whether the hitting-time approach extends to counting spanning forests or other deletion-contraction invariants.

Load-bearing premise

The combinatorial derivation of the hitting-time formula accounts for every boundary condition and symmetry reduction on the wheel without omitted terms or hidden case distinctions.

What would settle it

Compute the number of spanning trees by direct enumeration on small identified wheel graphs (N=3 and N=4) and check whether the numbers match the closed form obtained from the hitting-time formula.

read the original abstract

In this paper, we provide an exact formula for the average hitting times in a wheel graph $W_{N+1}$ using a combinatorial approach. For this wheel graph, the average hitting times can be expressed using Fibonacci numbers when the number of surrounding vertices is odd and Lucas numbers when it is even. Furthermore, combining the exact formula for the average hitting times with the general formula for the effective resistance of the graph allows determination of the number of spanning trees of the graph with two identified vertices.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives closed forms for hitting times on wheels (Fibonacci/Lucas by parity) then substitutes into effective resistance to count spanning trees after vertex identification, but supplies no small-N checks.

read the letter

The core contribution is an explicit formula for spanning trees in the wheel after identifying two vertices, reached by first finding average hitting times via a combinatorial recurrence and then using the known effective-resistance identity. The hitting-time expressions split by parity of the rim size and land on Fibonacci or Lucas numbers, which is a clean closed form if the recurrence holds. That part is the actual new piece; prior work on wheel hitting times exists but this specific link to the contracted spanning-tree count does not appear to be standard. The method itself is straightforward and avoids matrix inversion, which is a practical plus for this family of graphs. The main weakness is the complete absence of verification. No table of small-N values appears, no direct count of spanning trees on the identified graph is shown, and no comparison is made to the many known closed forms for wheel spanning trees or their contractions. Without those checks it is impossible to confirm that the boundary conditions after identification were handled correctly in the recurrence. The stress-test worry about omitted terms at the merged vertex therefore cannot be dismissed from the abstract alone. This is narrow enumerative graph theory. A reader already working on random walks or tree enumeration on small-world graphs would find the formulas useful if they check out. It is solid enough on its own terms to deserve referee time rather than a desk reject, provided the authors add the missing small-case comparisons.

Referee Report

2 major / 0 minor

Summary. The manuscript claims an exact combinatorial derivation of average hitting times on the wheel graph W_{N+1}, yielding closed forms in Fibonacci numbers (odd rim size) or Lucas numbers (even rim size). It then substitutes this expression into a general effective-resistance formula to obtain the number of spanning trees after identifying two vertices.

Significance. If the derivation is correct, the result supplies a closed-form spanning-tree count for this contracted wheel family, extending known wheel-graph enumerations and illustrating a hitting-time route to effective resistance. The Fibonacci/Lucas connection would indicate a clean linear-recurrence structure.

major comments (2)

[Abstract] Abstract and central derivation: the claim of an exact combinatorial formula rests on an uninspectable reduction; no recurrence, no small-N verification against the linear system for hitting times, and no explicit boundary-condition handling for the merged vertex are supplied, so the subsequent substitution into the effective-resistance identity cannot be checked for omitted terms or hidden case splits.
[Hitting-time derivation] Hitting-time section (presumed §3): the symmetry reduction for the identified-vertex case must encode modified transition probabilities and absorbing/reflecting conditions at the merged vertex; without an explicit recurrence or matrix inversion check on small N, it is impossible to confirm that the Fibonacci/Lucas expressions remain valid after identification.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed reading and for identifying points where the presentation can be strengthened. The concerns center on verifiability of the hitting-time derivation and its use in the spanning-tree count. We will revise the manuscript to supply the requested explicit elements.

read point-by-point responses

Referee: [Abstract] Abstract and central derivation: the claim of an exact combinatorial formula rests on an uninspectable reduction; no recurrence, no small-N verification against the linear system for hitting times, and no explicit boundary-condition handling for the merged vertex are supplied, so the subsequent substitution into the effective-resistance identity cannot be checked for omitted terms or hidden case splits.

Authors: We agree that the current presentation leaves the reduction steps insufficiently explicit for independent verification. In the revised manuscript we will insert the linear recurrence satisfied by the hitting times, tabulate explicit solutions for small N (N=3 to N=8) obtained both from the closed form and from direct solution of the linear system, and spell out the boundary conditions at the identified vertex, including the adjusted transition probabilities. These additions will also make the substitution into the effective-resistance formula fully traceable, with any case distinctions written out. revision: yes
Referee: [Hitting-time derivation] Hitting-time section (presumed §3): the symmetry reduction for the identified-vertex case must encode modified transition probabilities and absorbing/reflecting conditions at the merged vertex; without an explicit recurrence or matrix inversion check on small N, it is impossible to confirm that the Fibonacci/Lucas expressions remain valid after identification.

Authors: The symmetry reduction does incorporate the modified transitions at the merged vertex, but the manuscript does not display the resulting recurrence or the small-N matrix checks. We will add both: the recurrence obtained after collapsing the two vertices, together with a side-by-side comparison (for even and odd rim sizes) of the closed-form values against the numerical solution of the linear system on small instances. This will confirm that the Fibonacci/Lucas expressions continue to hold after identification. revision: yes

Circularity Check

0 steps flagged

Derivation uses independent combinatorial hitting-time formula plus external resistance identity

full rationale

The paper states it obtains the hitting-time closed forms (Fibonacci/Lucas) via a combinatorial approach on the wheel graph, then substitutes into an external general formula for effective resistance to recover the spanning-tree count after vertex identification. No self-citation is invoked for the core steps, no parameter is fitted and relabeled as a prediction, and the target quantity is not shown to equal the input expressions by algebraic identity or definition. The derivation chain therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard graph-theoretic definitions of hitting time and effective resistance plus an unstated combinatorial recurrence whose correctness is asserted but not displayed.

axioms (2)

standard math The commute time identity relating effective resistance to the sum of hitting times in both directions holds for any undirected graph.
Invoked when the hitting-time formula is substituted into the resistance expression.
domain assumption The wheel graph W_{N+1} admits a symmetry reduction that collapses the hitting-time equations to a linear recurrence solvable by Fibonacci/Lucas sequences.
Required for the closed-form claim; location not visible in abstract.

pith-pipeline@v0.9.0 · 5602 in / 1401 out tokens · 24840 ms · 2026-05-23T04:42:06.403652+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

Cost/FunctionalEquation washburn_uniqueness_aczel echoes

?

echoes
ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

the average hitting times can be expressed using Fibonacci numbers when the number of surrounding vertices is odd and Lucas numbers when it is even
Foundation/AlphaDerivationExplicit phi_golden_ratio echoes

?

echoes
ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

h(W_{N+1};0,ℓ)=4N(F_N−F_{N−2ℓ})/(F_{N−1}+F_{N+1}) (odd case) and analogous Lucas form

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

Aldous, D. J. : Hitting times for random walks on vertex-transitiv e graphs. Mathemat- ical Proceedings of the Cambridge Philosophical Society 106 179–191 (1989)

work page 1989
[2]

: On the average hitting times of the s quares of cycles

Doi, Y., Konno, N., Nakamigawa, T., Sakuma, T., Segawa, E., Shinoha ra, H., Tamura, S., Tanaka, Y., and Toyota, K. : On the average hitting times of the s quares of cycles. Discrete Applied Mathematics 313 18-28 (2022)

work page 2022
[3]

Kirchhoﬀ, G. : Uber die Auﬂ¨ osung der Gleichungen, auf welche ma n bei der Unter- suchung der linearen Verteilung galvanischer Str¨ ome gef¨ uhrt wird, Annalen Physik und Chemie 72 497-508 (1847)

work page
[4]

: Random walks on graphs: A survey

Lov´asz, L. : Random walks on graphs: A survey. Combinatorics, Paul Erd˝ os is eighty Vol. 2 (1993)

work page 1993
[5]

Myers, B. R. : Number of spanning trees in a wheel. IEEE Transactions on Circuit Theory CT-18, 280-282 (1971)

work page 1971
[6]

C. S. J. A. Nash-Williams. : Random walk and electric currents in net works. Proceedings of the Cambridge Philosophical Society. Mathematical and P hysical Sciences 55 181-194 (1959)

work page 1959
[7]

Nishimura

Y. Nishimura. : Average hitting times in some f -equitable graphs, https://arxiv.org/abs/2312.11848

work page arXiv
[8]

Sharavas, K. R. : Finding hitting times in various graphs. Statistics & Probability Letters 83 2067-2072 (2013)

work page 2067
[9]

: On the skeletons of a graph or digraph

Sedlacek, J. : On the skeletons of a graph or digraph. Proceedings of the Calgary International Conference of Combinatorial Structures and Their Applications, Gordon and Breach, 387-391 (1970)

work page 1970
[10]

: On the average hitting times of the directed wheel, in submitted

Tamura, S. : On the average hitting times of the directed wheel, in submitted

work page
[11]

: On the average hitting times of Cay( ZN , {+1, +2})

Tanaka, Y. : On the average hitting times of Cay( ZN , {+1, +2}). Discrete Applied Mathematics 343 269-276 (2024)

work page 2024
[12]

: On the average hitting times of weighted Cayley gra phs, https://arxiv.org/abs/2310.16571

Tanaka, Y. : On the average hitting times of weighted Cayley gra phs, https://arxiv.org/abs/2310.16571

work page arXiv
[13]

: Fibonacci and Lucas Numbers with Applications, Volume 1 , Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tract s (2018) 23

Thomas, K. : Fibonacci and Lucas Numbers with Applications, Volume 1 , Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tract s (2018) 23

work page 2018
[14]

: Fibonacci and Lucas Numbers with Applications, Volume 2 , Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tract s (2019)

Thomas, K. : Fibonacci and Lucas Numbers with Applications, Volume 2 , Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tract s (2019)

work page 2019
[15]

: Simple random walks on wheel graphs

Yang, Y. : Simple random walks on wheel graphs. Applied Mathematics & Information Sciences 6 123-128 (2012) 24

work page 2012

[1] [1]

Aldous, D. J. : Hitting times for random walks on vertex-transitiv e graphs. Mathemat- ical Proceedings of the Cambridge Philosophical Society 106 179–191 (1989)

work page 1989

[2] [2]

: On the average hitting times of the s quares of cycles

Doi, Y., Konno, N., Nakamigawa, T., Sakuma, T., Segawa, E., Shinoha ra, H., Tamura, S., Tanaka, Y., and Toyota, K. : On the average hitting times of the s quares of cycles. Discrete Applied Mathematics 313 18-28 (2022)

work page 2022

[3] [3]

Kirchhoﬀ, G. : Uber die Auﬂ¨ osung der Gleichungen, auf welche ma n bei der Unter- suchung der linearen Verteilung galvanischer Str¨ ome gef¨ uhrt wird, Annalen Physik und Chemie 72 497-508 (1847)

work page

[4] [4]

: Random walks on graphs: A survey

Lov´asz, L. : Random walks on graphs: A survey. Combinatorics, Paul Erd˝ os is eighty Vol. 2 (1993)

work page 1993

[5] [5]

Myers, B. R. : Number of spanning trees in a wheel. IEEE Transactions on Circuit Theory CT-18, 280-282 (1971)

work page 1971

[6] [6]

C. S. J. A. Nash-Williams. : Random walk and electric currents in net works. Proceedings of the Cambridge Philosophical Society. Mathematical and P hysical Sciences 55 181-194 (1959)

work page 1959

[7] [7]

Nishimura

Y. Nishimura. : Average hitting times in some f -equitable graphs, https://arxiv.org/abs/2312.11848

work page arXiv

[8] [8]

Sharavas, K. R. : Finding hitting times in various graphs. Statistics & Probability Letters 83 2067-2072 (2013)

work page 2067

[9] [9]

: On the skeletons of a graph or digraph

Sedlacek, J. : On the skeletons of a graph or digraph. Proceedings of the Calgary International Conference of Combinatorial Structures and Their Applications, Gordon and Breach, 387-391 (1970)

work page 1970

[10] [10]

: On the average hitting times of the directed wheel, in submitted

Tamura, S. : On the average hitting times of the directed wheel, in submitted

work page

[11] [11]

: On the average hitting times of Cay( ZN , {+1, +2})

Tanaka, Y. : On the average hitting times of Cay( ZN , {+1, +2}). Discrete Applied Mathematics 343 269-276 (2024)

work page 2024

[12] [12]

: On the average hitting times of weighted Cayley gra phs, https://arxiv.org/abs/2310.16571

Tanaka, Y. : On the average hitting times of weighted Cayley gra phs, https://arxiv.org/abs/2310.16571

work page arXiv

[13] [13]

: Fibonacci and Lucas Numbers with Applications, Volume 1 , Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tract s (2018) 23

Thomas, K. : Fibonacci and Lucas Numbers with Applications, Volume 1 , Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tract s (2018) 23

work page 2018

[14] [14]

: Fibonacci and Lucas Numbers with Applications, Volume 2 , Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tract s (2019)

Thomas, K. : Fibonacci and Lucas Numbers with Applications, Volume 2 , Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tract s (2019)

work page 2019

[15] [15]

: Simple random walks on wheel graphs

Yang, Y. : Simple random walks on wheel graphs. Applied Mathematics & Information Sciences 6 123-128 (2012) 24

work page 2012