Decomposing random regular graphs into stars

Abstract

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 ${\mathcal{G}}_{n,d}$. Using the small subgraph conditioning method, we prove an existence result for such decompositions for all $d,k$ such that $d/2<k\le d/2+\max \{1,\frac{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 ${\mathcal{G}}_{n,d}$ for all $d\le 100$ and $k>d/2$. For smaller values of $k$, the connection between $k$-star decompositions and ${\hat{I}}^2$-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 $2k^2+k\le d$, and (ii) when $k$ is odd and $k<d/2$.

44 pages. This version addresses referees comments