Fibonacci and Lucas numbers arising from two-component spanning forests of wheel graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912779547443200 |
|---|---|
| author | Miezaki, Tsuyoshi Tamura, Shunya |
| author_facet | Miezaki, Tsuyoshi Tamura, Shunya |
| contents | In this paper, we present a constructive bijection between a conditioned spanning forest of the wheel graph $W_{n+1}$ and a spanning tree of the fan graph $F_n$. In addition, by applying the effective resistance formula obtained by Bapat and Gupta \cite{bapat-gupta}, we derive an explicit formula for the number of two-component spanning forests of $W_{n+1}$ in which two specified vertices $u$ and $v$ lie in distinct components. Based on this result, we obtain explicit formulas for the following three conditioned two-component spanning forests $F_{W_{n+1}}(v_1\mid v_2)$, $F_{W_{n+1}}(v_1\mid v_3)$, and $F_{W_{n+1}}(v_1\mid v_c)$. These formulas are $F_{W_{n+1}}(v_1\mid v_2)=2(f_{2n-1}-1)$, $F_{W_{n+1}}(v_1\mid v_3)=2(\ell_{2n-2}-3)$, $F_{W_{n+1}}(v_1\mid v_c)=f_{2n}$, where $f_i$ and $\ell_j$ denote the $i$-th Fibonacci number and $j$-th Lucas number, respectively. As these identities show, the enumerations naturally lead to formulas involving Fibonacci numbers and Lucas numbers. Taken together, these two approaches show a unified perspective. One is the constructive combinatorial bijection, and the other is the analytic method based on effective resistance. Together they provide a new integrated framework for studying the structure of spanning forests on $W_{n+1}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_18214 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fibonacci and Lucas numbers arising from two-component spanning forests of wheel graphs Miezaki, Tsuyoshi Tamura, Shunya Combinatorics 05C30, 05C05, 05A19 In this paper, we present a constructive bijection between a conditioned spanning forest of the wheel graph $W_{n+1}$ and a spanning tree of the fan graph $F_n$. In addition, by applying the effective resistance formula obtained by Bapat and Gupta \cite{bapat-gupta}, we derive an explicit formula for the number of two-component spanning forests of $W_{n+1}$ in which two specified vertices $u$ and $v$ lie in distinct components. Based on this result, we obtain explicit formulas for the following three conditioned two-component spanning forests $F_{W_{n+1}}(v_1\mid v_2)$, $F_{W_{n+1}}(v_1\mid v_3)$, and $F_{W_{n+1}}(v_1\mid v_c)$. These formulas are $F_{W_{n+1}}(v_1\mid v_2)=2(f_{2n-1}-1)$, $F_{W_{n+1}}(v_1\mid v_3)=2(\ell_{2n-2}-3)$, $F_{W_{n+1}}(v_1\mid v_c)=f_{2n}$, where $f_i$ and $\ell_j$ denote the $i$-th Fibonacci number and $j$-th Lucas number, respectively. As these identities show, the enumerations naturally lead to formulas involving Fibonacci numbers and Lucas numbers. Taken together, these two approaches show a unified perspective. One is the constructive combinatorial bijection, and the other is the analytic method based on effective resistance. Together they provide a new integrated framework for studying the structure of spanning forests on $W_{n+1}$. |
| title | Fibonacci and Lucas numbers arising from two-component spanning forests of wheel graphs |
| topic | Combinatorics 05C30, 05C05, 05A19 |
| url | https://arxiv.org/abs/2512.18214 |