Kenta Noguchi ; Carol T. Zamfirescu - Spanning trees for many different numbers of leaves

dmtcs:13116 - Discrete Mathematics & Theoretical Computer Science, November 18, 2024, vol. 26:3 - https://doi.org/10.46298/dmtcs.13116
Spanning trees for many different numbers of leavesArticle

Authors: Kenta Noguchi ; Carol T. Zamfirescu

    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.


    Volume: vol. 26:3
    Section: Graph Theory
    Published on: November 18, 2024
    Accepted on: October 31, 2024
    Submitted on: February 26, 2024
    Keywords: Mathematics - Combinatorics,05C05 (Primary) 05C10 (Secondary)

    Consultation statistics

    This page has been seen 21 times.
    This article's PDF has been downloaded 9 times.