Pham Hoang Ha ; Nguyen Gia Hien - Spanning trees of claw-free graphs with few leaves and branch vertices

dmtcs:15247 - Discrete Mathematics & Theoretical Computer Science, November 20, 2025, vol. 27:3 - https://doi.org/10.46298/dmtcs.15247
Spanning trees of claw-free graphs with few leaves and branch verticesArticle

Authors: Pham Hoang Ha ; Nguyen Gia Hien

    Let $T$ be a tree. A vertex of degree one is a \emph{leaf} of $T$ and a vertex of degree at least three is a \emph{branch vertex} of $T$. A graph is said to be claw-free if it does not contain $K_{1,3}$ as an induced subgraph. In this paper, we study the spanning trees with a bounded number of leaves and branch vertices of claw-free graphs. Applying the main results, we also give some improvements of previous results on the spanning trees with few branch vertices for the case of claw-free graphs.

    arXiv admin note: text overlap with arXiv:2201.01043


    Volume: vol. 27:3
    Section: Graph Theory
    Published on: November 20, 2025
    Accepted on: November 8, 2025
    Submitted on: February 17, 2025
    Keywords: Combinatorics

    Consultation statistics

    This page has been seen 110 times.
    This article's PDF has been downloaded 47 times.