On the star arboricity of hypercubes

Abstract

A Hypercube $Q_n$ is a graph in which the vertices are all binary vectors of length n, and two vertices are adjacent if and only if their components differ in exactly one place. A galaxy or a star forest is a union of vertex disjoint stars. The star arboricity of a graph $G$, $\mathrm{sa}(G)$, is the minimum number of galaxies which partition the edge set of $G$. In this paper among other results, we determine the exact values of $\mathrm{sa}(Q_n)$ for $n\in \{2^k-3,2^k+1,2^k+2,2^i+2^j-4\}$, $i\ge j\ge 2$. We also improve the last known upper bound of $\mathrm{sa}(Q_n)$ and show the relation between $\mathrm{sa}(G)$ and square coloring.

Australas. J. Combin., vol. 59 pt. 2, (2014)