Spanning trees for many different numbers of leaves
| Autor: | Noguchi, Kenta, Zamfirescu, Carol T. |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Let $G$ be a connected graph and $L(G)$ the set of all integers $k$ such that $G$ contains a spanning tree with exactly $k$ leaves. We show that for a connected graph $G$, the set $L(G)$ is contiguous. It follows from work of Chen, Ren, and Shan that every connected and locally connected $n$-vertex graph -- this includes triangulations -- has a spanning tree with at least $n/2 + 1$ leaves, so by a classic theorem of Whitney and our result, in any plane $4$-connected $n$-vertex triangulation one can find for any integer $k$ which is at least~2 and at most $n/2 + 1$ a spanning tree with exactly $k$ leaves (and each of these trees can be constructed in polynomial time). We also prove that there exist infinitely many $n$ such that there is a plane $4$-connected $n$-vertex triangulation containing a spanning tree with $2n/3$ leaves, but no spanning tree with more than $2n/3$ leaves. Comment: 7 pages, 1 figure |
| Databáze: | arXiv |
| Externí odkaz: |
|