Effective resistance and spanning trees in complete graphs with distance-class deletions
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917490247860224 |
|---|---|
| author | Tamura, Shunya |
| author_facet | Tamura, Shunya |
| contents | In this paper, we consider circulant graphs obtained from the complete graph $K_N$ by deleting all edges belonging to a prescribed distance class. We study, in a unified manner, the effective resistance, the expected hitting time, the number of spanning trees, and the number of two-component spanning forests of these graphs. For general distance-class deletions, these quantities admit natural spectral representations in terms of the Laplacian eigenvalues. However, such representations typically remain at the level of finite Fourier sums, and concise closed forms are not expected in general. We focus on the case of a single deleted distance class. When the number of vertices $N$ is odd and $\gcd(r,N)=1$, the graph $G_{N,r}$ is isomorphic to $G_{N,1}$. In this setting, we derive explicit exponential-type formulas for the effective resistance and the number of spanning trees, and obtain corresponding closed expressions for two-component spanning forests and expected hitting times. Our results show that the case $r=2$ is not essentially new, but follows from a general isomorphism structure underlying distance-class deletions. We also clarify the relation of our formulas to earlier results on the complete graph with a Hamiltonian cycle removed, and provide a unified derivation within a spectral framework. Moreover, by asymptotic analysis, we show that the ratio $τ(G_{N,1})/τ(K_N)$ converges to $e^{-2}$ as $N \to \infty$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_08921 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Effective resistance and spanning trees in complete graphs with distance-class deletions Tamura, Shunya Combinatorics 05C50, 05C12, 05C30 In this paper, we consider circulant graphs obtained from the complete graph $K_N$ by deleting all edges belonging to a prescribed distance class. We study, in a unified manner, the effective resistance, the expected hitting time, the number of spanning trees, and the number of two-component spanning forests of these graphs. For general distance-class deletions, these quantities admit natural spectral representations in terms of the Laplacian eigenvalues. However, such representations typically remain at the level of finite Fourier sums, and concise closed forms are not expected in general. We focus on the case of a single deleted distance class. When the number of vertices $N$ is odd and $\gcd(r,N)=1$, the graph $G_{N,r}$ is isomorphic to $G_{N,1}$. In this setting, we derive explicit exponential-type formulas for the effective resistance and the number of spanning trees, and obtain corresponding closed expressions for two-component spanning forests and expected hitting times. Our results show that the case $r=2$ is not essentially new, but follows from a general isomorphism structure underlying distance-class deletions. We also clarify the relation of our formulas to earlier results on the complete graph with a Hamiltonian cycle removed, and provide a unified derivation within a spectral framework. Moreover, by asymptotic analysis, we show that the ratio $τ(G_{N,1})/τ(K_N)$ converges to $e^{-2}$ as $N \to \infty$. |
| title | Effective resistance and spanning trees in complete graphs with distance-class deletions |
| topic | Combinatorics 05C50, 05C12, 05C30 |
| url | https://arxiv.org/abs/2605.08921 |