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 279 times.
This article's PDF has been downloaded 204 times.