TY - JOUR

T1 - Conditions for Implicit-Degree Sum for Spanning Trees with Few Leaves in K1,4-Free Graphs

AU - Cai, Junqing

AU - Lin, Cheng Kuan

AU - Sun, Qiang

AU - Wang, Panpan

N1 - Publisher Copyright:
© 2023 by the authors.

PY - 2023/12

Y1 - 2023/12

N2 - A graph with n vertices is called an n-graph. A spanning tree with at most k leaves is referred to as a spanning k-ended tree. Spanning k-ended trees are important in various fields such as network design, graph theory, and communication networks. They provide a structured way to connect all the nodes in a network while ensuring efficient communication and minimizing unnecessary connections. In addition, they serve as fundamental components for algorithms in routing, broadcasting, and spanning tree protocols. However, determining whether a connected graph has a spanning k-ended tree or not is NP-complete. Therefore, it is important to identify sufficient conditions for the existence of such trees. The implicit-degree proposed by Zhu, Li, and Deng is an important indicator for the Hamiltonian problem and the spanning k-ended tree problem. In this article, we provide two sufficient conditions for K1,4-free connected graphs to have spanning k-ended trees for k = 2, 3. We prove the following: Let G be a K1,4-free connected n-graph. For k = 2, 3, if the implicit-degree sum of any k + 1 independent vertices of G is at least n − k + 2, then G has a spanning k-ended tree. Moreover, we give two examples to show that the lower bounds n and n − 1 are the best possible.

AB - A graph with n vertices is called an n-graph. A spanning tree with at most k leaves is referred to as a spanning k-ended tree. Spanning k-ended trees are important in various fields such as network design, graph theory, and communication networks. They provide a structured way to connect all the nodes in a network while ensuring efficient communication and minimizing unnecessary connections. In addition, they serve as fundamental components for algorithms in routing, broadcasting, and spanning tree protocols. However, determining whether a connected graph has a spanning k-ended tree or not is NP-complete. Therefore, it is important to identify sufficient conditions for the existence of such trees. The implicit-degree proposed by Zhu, Li, and Deng is an important indicator for the Hamiltonian problem and the spanning k-ended tree problem. In this article, we provide two sufficient conditions for K1,4-free connected graphs to have spanning k-ended trees for k = 2, 3. We prove the following: Let G be a K1,4-free connected n-graph. For k = 2, 3, if the implicit-degree sum of any k + 1 independent vertices of G is at least n − k + 2, then G has a spanning k-ended tree. Moreover, we give two examples to show that the lower bounds n and n − 1 are the best possible.

KW - K-free graph

KW - implicit-degree

KW - leaves

KW - spanning tree

UR - http://www.scopus.com/inward/record.url?scp=85180244760&partnerID=8YFLogxK

U2 - 10.3390/math11244981

DO - 10.3390/math11244981

M3 - Article

AN - SCOPUS:85180244760

SN - 2227-7390

VL - 11

JO - Mathematics

JF - Mathematics

IS - 24

M1 - 4981

ER -