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

A u t (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

m z_{2}^{n}

of order

2^{n}

. In this paper, we prove that

S Q_{n}

is a 4-Cayley graph of

m z_{2}^{n - 2}

when

n g e q 6

, and is a

l f l o o r n / 2 f l o o r

-Cayley graph when

n l e q 5

. This symmetric property shows that an

n

-dimensional spined cube with

n g e q 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 g e q 4

. Moreover, we determine the vertex-transitivity of

S Q_{n}

, and prove that

S Q_{n}

is not vertex-transitive unless

n l e q 3

.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Symmetric property and edge-disjoint Hamiltonian cycles of the spined cube