论文标题
对称特性和边缘 - 偶型汉密尔顿周期
Symmetric property and edge-disjoint Hamiltonian cycles of the spined cube
论文作者
论文摘要
旋转的立方体$ sq_n $是Zhou等人介绍的HyperCube $ q_n $的变体。在[信息处理信件111（2011）561-567]中，作为用于并行计算的互连网络。图形$ \ g $是$ M $ -CAYLEY图，如果其自动形态组$ \ aut（\ g）$具有在带有$ m $ orbits的顶点集合上的半连接子组，如果它是1-Cayley图，则是Caley Graph。众所周知，$ q_n $是基础Abelian 2组$ \ mz_2^n $ of订单$ 2^n $的Cayley图。在本文中，我们证明$ sq_n $是$ \ mz_2^{n-2} $的4间 - $ n \ geq6 $时，并且是$ \ lfloor n/2 \ rfloor $ -cayley $ -cayley $ -Cayley Graph时$ n \ leq 5 $。该对称的属性表明，可以将$ n $二维的固定立方体带有$ n \ geq6 $分解为八个vertex-dischoint $（n-3）$ - 尺寸超级立方体，作为应用程序，证明存在两个$ n $ n $ n \ geq的$ n $ n $ n \ geq的边缘 - edisch-dischoint hamiltonian Cycles。此外，我们确定$ sq_n $的顶点传递性，并证明$ sq_n $不是顶点传输，除非$ n \ leq3 $。
The spined cube $SQ_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 $SQ_n$ is a 4-Cayley graph of $\mz_2^{n-2}$ when $n\geq6$, and is a $\lfloor n/2\rfloor$-Cayley graph when $n\leq 5$. This symmetric property shows that an $n$-dimensional spined cube with $n\geq6$ 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 $SQ_n$ when $n\geq4$. Moreover, we determine the vertex-transitivity of $SQ_n$, and prove that $SQ_n$ is not vertex-transitive unless $n\leq3$.
