Spanning trees of K_1,4-free graphs with a bounded number of leaves and branch vertices

2022/01/04 by Pham Hoang Ha, Ha, Pham Hoang
Computer Science · Mathematics · #05C05 #05C07 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2201.01043

openalex publication_date 2022/01/04 · openalex created_date 2022/04/03 · openalex updated_date 2026/07/28

Abstract

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

Related

• Spanning trees of K_1,4-free graphs whose reducible stems have few leaves
• Spanning trees of claw-free graphs with few leaves and branch vertices
• A note on spanning trees of connected K_1,t-free graphs whose stems\n have a few leaves
• Spanning trees with at most 5 leaves and branch vertices in total of K_1,5-free graphs
• Spanning trees with at most 4 leaves in K_1,5-free graphs