The Orbits of Twisted Crossed Cubes

Abstract

Two vertices u and v in a graph G=(V,E) are in the same orbit if there exists an automorphism ϕ of G such that ϕ(u)=v. The orbit number of a graph G, denoted by Orb(G), is the number of orbits that partition V(G). All vertex-transitive graphs G satisfy Orb(G)=1. Since the n-dimensional hypercube, denoted by Qn, is vertex-transitive, it follows that Orb(Qn)=1 for n≥1. The twisted crossed cube, denoted by TCQn, is a variant of the hypercube. In this paper, we prove that Orb(TCQn)=1 if n≤4, Orb(TCQ5)=Orb(TCQ6)=2, and Orb(TCQn)=2⌊n−12⌋ if n≥7.

Keywords

• twisted crossed cubes
• automorphism
• vertex-transitive
• orbits