Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2605.03583 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911648343654400 |
|---|---|
| author | Wagner, Stephan Wang, Ruoyu |
| author_facet | Wagner, Stephan Wang, Ruoyu |
| contents | For a graph $G$ with $n$ vertices and a positive integer $k \leq n$, let $s_k(G)$ be the number of subtrees (subgraphs that are trees, not necessarily induced) of $G$ with $k$ vertices. The subtree polynomial of $G$ is $S(G;x) = \sum_{k=1}^n s_k(G) x^k$. In this paper, we consider dense connected graphs with a minimum degree that is linear in the number of vertices. We prove that the number of missing vertices in a random subtree is asymptotically Poisson-distributed and deduce that all the roots of the subtree polynomial have to be close to $0$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_03583 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Distribution Of Subtrees In Dense Graphs And The Roots Of The Subtree Polynomial Wagner, Stephan Wang, Ruoyu Combinatorics For a graph $G$ with $n$ vertices and a positive integer $k \leq n$, let $s_k(G)$ be the number of subtrees (subgraphs that are trees, not necessarily induced) of $G$ with $k$ vertices. The subtree polynomial of $G$ is $S(G;x) = \sum_{k=1}^n s_k(G) x^k$. In this paper, we consider dense connected graphs with a minimum degree that is linear in the number of vertices. We prove that the number of missing vertices in a random subtree is asymptotically Poisson-distributed and deduce that all the roots of the subtree polynomial have to be close to $0$. |
| title | The Distribution Of Subtrees In Dense Graphs And The Roots Of The Subtree Polynomial |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.03583 |