Geodesic
Spanning trees for many different numbers of leaves
Discrete mathematics & theoretical computer science, Tome 26 (2024) no. 3.

Voir la notice de l'article provenant de la source Episciences

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.
DOI : 10.46298/dmtcs.13116
Classification : 05C05, 05C10 
@article{DMTCS_2024_26_3_a14,
     author = {Noguchi, Kenta and Zamfirescu, Carol T.},
     title = {Spanning trees for many different numbers of leaves},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {26},
     number = {3},
     year = {2024},
     doi = {10.46298/dmtcs.13116},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.13116/}
}
TY  - JOUR
AU  - Noguchi, Kenta
AU  - Zamfirescu, Carol T.
TI  - Spanning trees for many different numbers of leaves
JO  - Discrete mathematics & theoretical computer science
PY  - 2024
VL  - 26
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.13116/
DO  - 10.46298/dmtcs.13116
LA  - en
ID  - DMTCS_2024_26_3_a14
ER  - 
%0 Journal Article
%A Noguchi, Kenta
%A Zamfirescu, Carol T.
%T Spanning trees for many different numbers of leaves
%J Discrete mathematics & theoretical computer science
%D 2024
%V 26
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.13116/
%R 10.46298/dmtcs.13116
%G en
%F DMTCS_2024_26_3_a14
Noguchi, Kenta; Zamfirescu, Carol T. Spanning trees for many different numbers of leaves. Discrete mathematics & theoretical computer science, Tome 26 (2024) no. 3. doi : 10.46298/dmtcs.13116. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.13116/

Cité par Sources :