On the Orbits of Crossed Cubes

Abstract

An orbit of $G$ is a subset $S$ of $V(G)$ such that $\varphi (u)=v$ for any two vertices $u,v\in S$, where $\varphi$ is an isomorphism of $G$. The orbit number of a graph $G$, denoted by $\text{Orb}(G)$, is the number of orbits of $G$. In [A Note on Path Embedding in Crossed Cubes with Faulty Vertices, Information Processing Letters 121 (2017) pp. 34--38], Chen et al. conjectured that $\text{Orb}({\text{CQ}}_n)=2^{\lceil \frac{n}{2}\rceil -2}$ for $n⩾3$, where ${\text{CQ}}_n$ denotes an $n$-dimensional crossed cube. In this paper, we settle the conjecture.

15 pages