Star-factors in graphs of high degree

2016/11/15 by Rajko Nenadov, Nenadov, Rajko
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1611.04712

openalex publication_date 2016/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that every graph with sufficiently large minimum degree d contains a spanning forest in which every component is a star of size at least √(d) - O(d^1/4). This improves the result of Alon and Wormald and is optimal up to the lower order term.

Citations

• On the maximal number of independent circuits in a graph

Related

• High degree graphs contain large-star factors
• On spanning trees with high internal degree
• Star-uniform Graphs
• Uniform Star-factors of Graphs with Girth Three
• Star-factors of tournaments