Symmetric property and edge-disjoint Hamiltonian cycles of the spined cube

Abstract

The spined cube $S{Q}_n$ is a variant of the hypercube $Q_n$, introduced by Zhou et al. in [Information Processing Letters 111 (2011) 561-567] as an interconnection network for parallel computing. A graph $\G$ is an $m$-Cayley graph if its automorphism group $\Aut(\G)$ has a semiregular subgroup acting on the vertex set with $m$ orbits, and is a Caley graph if it is a 1-Cayley graph. It is well-known that $Q_n$ is a Cayley graph of an elementary abelian 2-group $\mz_2^n$ of order $2^n$. In this paper, we prove that $S{Q}_n$ is a 4-Cayley graph of $\mz_2^{n-2}$ when $n\ge 6$, and is a $\lfloor n/2\rfloor$-Cayley graph when $n\le 5$. This symmetric property shows that an $n$-dimensional spined cube with $n\ge 6$ can be decomposed to eight vertex-disjoint $(n-3)$-dimensional hypercubes, and as an application, it is proved that there exist two edge-disjoint Hamiltonian cycles in $S{Q}_n$ when $n\ge 4$. Moreover, we determine the vertex-transitivity of $S{Q}_n$, and prove that $S{Q}_n$ is not vertex-transitive unless $n\le 3$.

12 pages