2023/08/30 by Michelle Delcourt, Catherine Greenhill, Delcourt, Michelle +7 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2308.16037
openalex publication_date 2023/08/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
We study k-star decompositions, that is, partitions of the edge set into disjoint stars with k edges, in the uniformly random d-regular graph model Gn,d. Using the small subgraph conditioning method, we prove an existence result for such decompositions for all d,k such that d/2 < k ≤ d/2 + max\1,(1)/(6)log d\. More generally, we give a sufficient existence condition that can be checked numerically for any given values of d and k. Complementary negative results are obtained using the independence ratio of random regular graphs. Our results establish an existence threshold for k-star decompositions in Gn,d for all d≤ 100 and k > d/2. For smaller values of k, the connection between k-star decompositions and β-orientations allows us to apply results of Thomassen (2012) and Lovász, Thomassen, Wu and Zhang (2013). We prove that random d-regular graphs satisfy their assumptions with high probability, thus establishing a.a.s. existence of k-star decompositions (i) when 2k2+k≤ d, and (ii) when k is odd and k < d/2.