What is the minimum number of star graphs $S_4$ required to fully cover a 4-dimensional hypercube graph $Q_4$? How about the number of $S_5$ star graphs necessary to cover the 5-dimensional hypercube graph $Q_5$? Finally, what about the 6-dimensional case?
For the 4-dimensional case, I keep getting that we need $4$ star graphs, but what if there's a way to cover it with $3$ star graphs? I don't have an algorithmic approach, and honestly, drawing these higher-dimension hypercubes is an arduous task. Could someone propose how to attain those coverings?
$Q_n$ has $n 2^{n-1}$ edges and $S_n$ has $n$ edges, therefore at least $\frac{n 2^{n-1}}{n} = 2^{n-1}$ $S_n$ are needed to cover the edges of the cube.
Also, $Q_n$ is bipartite graph. Each vertex and its incident edges forms a an $S_n$ of $Q_n$. If you take the vertices of one part and their incident edges you get exactly $2^{n-1}$ stars $S_n$ that cover all the edges of $Q_n$