Edge-Defect Spectral Methods for Higher-Order Rankings of Spanning Tree Counts
Abstract
In this paper, we study the higher-order ranking, by spanning-tree count, of graphs obtained from a complete graph by deleting a fixed number of edges. Using the edge-defect matrix determined by the deleted edges and the interaction number measuring the local overlap among them, we derive a stability inequality that quantitatively estimates the decrease in the number of spanning trees from the matching-deletion case. Combining this stability estimate with a classification of deletion graphs having small interaction number, we determine, up to isomorphism, the nine deletion graphs with the largest spanning-tree counts for p≥6 and n≥2p. We also clarify the relation between the interaction number, the local structure of the deletion graph, and the decrease in the number of spanning trees through a logarithmic expansion of the normalized spanning-tree count.
Related
- From intersection names to street rankings in Kyoto: Comparing ranking methods for incomplete pairwise data
- Spectral radius and edge-disjoint spanning trees of graphs with edge connectivity
- Some results on the distance spectral radius and edge-disjoint spanning trees of graphs
- Maximum and Minimum Spectral Radii in an Exceptional Family for Edge-Disjoint Spanning Trees
- Higher rank spectral projector estimates and a Stein--Tomas restriction theorem
BibTeX
@misc{tamura2026edgedefect,
title = {{Edge-Defect Spectral Methods for Higher-Order Rankings of Spanning Tree Counts}},
author = {Shunya Tamura and José Luis Palacios},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33979},
eprint = {2609.33979},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33979},
}
RIS
TY - UNPB
TI - Edge-Defect Spectral Methods for Higher-Order Rankings of Spanning Tree Counts
AU - Shunya Tamura
AU - José Luis Palacios
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33979
UR - https://arxiv.org/abs/2609.33979
AB - In this paper, we study the higher-order ranking, by spanning-tree count, of graphs obtained from a complete graph by deleting a fixed number of edges. Using the edge-defect matrix determined by the deleted edges and the interaction number measuring the local overlap among them, we derive a stability inequality that quantitatively estimates the decrease in the number of spanning trees from the matching-deletion case. Combining this stability estimate with a classification of deletion graphs having small interaction number, we determine, up to isomorphism, the nine deletion graphs with the largest spanning-tree counts for p≥6 and n≥2p. We also clarify the relation between the interaction number, the local structure of the deletion graph, and the decrease in the number of spanning trees through a logarithmic expansion of the normalized spanning-tree count.
ER -