2022/10/29 by Yang, Da-Wei, Xu, Zihao, Feng, Yan-Quan +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2210.16603
The spined cube SQn is a variant of the hypercube Qn, 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 Qn is a Cayley graph of an elementary abelian 2-group \mz2n of order 2n. In this paper, we prove that SQn is a 4-Cayley graph of \mz2n-2 when n≥6, and is a \lfloor n/2\rfloor-Cayley graph when n≤ 5. This symmetric property shows that an n-dimensional spined cube with n≥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 SQn when n≥4. Moreover, we determine the vertex-transitivity of SQn, and prove that SQn is not vertex-transitive unless n≤3.