Spanning trees with at most \(5\) leaves and branch vertices in total of \(K_{1,5}\)-free graphs (Q6619687)

This research article focuses on the properties of spanning trees in connected graphs. The main objective of the paper is to prove that every \(n\)-vertex connected \(K_{1,5}\)-free graph \(G\) contains a spanning tree with at most 5 leaves and branch vertices in total. Moreover, the degree sum condition ``\(\sigma_4(G) \geq n-1\)'' is best possible. The primary objective is to determine conditions under which such graphs have spanning trees with a bounded number of leaves and branch vertices.\N\NThis work builds on prior studies of spanning trees in \( K_{1,r} \)-free and claw-free graphs, extending known results to the \( K_{1,5} \)-free case. The motivation stems from the theoretical importance of degree sum conditions in ensuring spanning tree properties and their potential applications in network design and optimization.\N\NThe problem centers around finding sufficient conditions for the existence of spanning trees in connected \( K_{1,5} \)-free graphs with at most five leaves and branch vertices combined. The authors define \( \sigma_k(G) \) as the minimum sum of degrees of \( k \)-independent vertices in the graph \( G \), and they focus on the condition \( \sigma_4(G) \geq n - 1 \), where \( n \) is the number of vertices in the graph.\N\NThe main challenge is to establish whether this degree sum condition is both sufficient and optimal for the existence of such spanning trees. Additionally, the authors aim to demonstrate that relaxing the condition \( \sigma_4(G) \geq n - 1 \) results in failure to guarantee the desired properties.\N\NThe authors prove the following main theorem:\N\NTheorem 1.7: If \( G \) is a connected \( K_{1,5} \)-free graph with \( n \) vertices and \( \sigma_4(G) \geq n - 1 \), then \( G \) contains a spanning tree with at most 5 leaves and branch vertices combined.\N\begin{itemize}\N\item[1.] The authors employ a maximal tree \( T \) with specific properties and recursively construct spanning trees that satisfy the given conditions.\N\item[2.] They show that the degree sum condition \( \sigma_4(G) \geq n - 1 \) ensures the existence of such trees and that any spanning tree exceeding these bounds violates the theorem.\N\item[3.] The authors provide a counterexample to illustrate that the degree sum condition cannot be relaxed further without losing the desired property.\N\end{itemize}\N\NAdditionally, they derive the following corollary:\N\NCorollary 1.8: If \( \sigma_4(G) \geq n - 1 \), \( G \) contains a spanning tree with at most one branch vertex.\N\NWith this corollary, the authors claim and prove that the set of leaves is an independent set in \( G \).\N\NThe authors also reference prior works and integrate them into their proof structure, particularly leveraging ideas from \textit{Y. Chen} et al. [Discrete Math. 342, No. 8, 2342--2349 (2019; Zbl 1418.05050)] and others to extend results from \( K_{1,4} \)-free to \( K_{1,5} \)-free graphs.\N\NThis paper establishes a significant result in the study of spanning trees in \( K_{1,5} \)-free graphs, proving that the degree sum condition \( \sigma_4(G) \geq n - 1 \) is sufficient and optimal for the existence of a spanning tree with at most 5 leaves and branch vertices combined. The authors also show that any relaxation of this condition fails to guarantee such a spanning tree.\N\begin{itemize}\N\item Generalization to Higher \( K_{1,r} \)-Free Graphs: Extending the results to \( K_{1,6} \)-free or higher \( K_{1,r} \)-free graphs could broaden the scope of the findings.\N\item Applications: Exploring real-world applications of spanning trees with bounded leaves and branch vertices in areas like network design or circuit layout optimization.\N\item Algorithmic Approaches Developing efficient algorithms to construct such spanning trees in \( K_{1,r} \)-free graphs based on the proven degree sum conditions.\N\end{itemize}\N\NThis work provides a robust foundation for further exploration in both theoretical and applied graph theory.