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

Junqing Cai, Cheng-Kuan Lin (), Qiang Sun and Panpan Wang
Additional contact information
Junqing Cai: School of Mathematical Science, Tianjin Normal University, Tianjin 300387, China
Cheng-Kuan Lin: Department of Computer Science, National Yang Ming Chiao Tung University, Hsinchu 30010, Taiwan
Qiang Sun: School of Mathematical Science, Yangzhou University, Yangzhou 225009, China
Panpan Wang: School of Mathematics and Statistics, Beijing Institute of Technology, Beijing 100081, China

Mathematics, 2023, vol. 11, issue 24, 1-13

Abstract: 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 K 1,4 -free connected graphs to have spanning k -ended trees for k = 2, 3. We prove the following: Let G be a K 1,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.

Keywords: implicit-degree; spanning tree; leaves; K 1,4 -free graph (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/24/4981/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/24/4981/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:24:p:4981-:d:1301776

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().