On the extrema of the mean subtree order of graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912557718044672 |
|---|---|
| author | Cambie, Stijn Jooken, Jorik Wagner, Stephan |
| author_facet | Cambie, Stijn Jooken, Jorik Wagner, Stephan |
| contents | It has been conjectured that the minimum and maximum of the mean subtree order among connected graphs of order $n$ are attained by the path $P_n$ and clique $K_n$, respectively. Extending ideas due to Haslegrave and Vince, we confirm that the minimum is indeed attained by $P_n$. On the other hand, we discuss different approaches (both promising and flawed) that could lead to a proof of the extremality of $K_n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_20593 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the extrema of the mean subtree order of graphs Cambie, Stijn Jooken, Jorik Wagner, Stephan Combinatorics 05C05, 05C35, 05C40 It has been conjectured that the minimum and maximum of the mean subtree order among connected graphs of order $n$ are attained by the path $P_n$ and clique $K_n$, respectively. Extending ideas due to Haslegrave and Vince, we confirm that the minimum is indeed attained by $P_n$. On the other hand, we discuss different approaches (both promising and flawed) that could lead to a proof of the extremality of $K_n$. |
| title | On the extrema of the mean subtree order of graphs |
| topic | Combinatorics 05C05, 05C35, 05C40 |
| url | https://arxiv.org/abs/2508.20593 |