Consider the embedding of a graph G₁ = (V₁, E₁) into a graph G₂ = (V₂, E₂) as a mapping &psgr;: V1 ← V₂. The dilation of the embedding &psgr; is defined as:

dil(G₁, G₂, &psgr;) = max{dist(G₂, &psgr; (u), &psgr; (v))|u, v ∈ V₁},

where dist(G₂, &psgr; (u), &psgr; (v)) denotes the distance between the two nodes &psgr; (u) and &psgr; (v) of G₂.

The dilation of an embedding is significant in using graphs to model communication systems. Thus, a smaller dilation implies a shorter communication delay in the simulation of the graph G₁ by the graph G₂.

Hypercubes Q_n are popular interconnection networks because of their relatively low node degree and diameter, higher connectivity, symmetry, and so on. Crossed cubes are important variants of hypercubes. The n-dimensional crossed cube CQ_n is defined recursively, where CQ₁ is the complete graph on two nodes whose addresses are 0 and 1. CQ_n consists of two subcubes CQ_n-1⁰ and CQ_n-1¹. The nodes u = u_n-1u_n-2 and u₁u₀ of CQ_n-1⁰ and v = v_n-1v_n-2 . . . v1v₀ of CQ_n-1¹, where u_n-1 = 0 and v_n-1 = 1, are joined by an edge in CQ_n if and only if u_n-2 = v_n-2 if n is even and if u_2i+1u_2i ~ v_2i+1v_2i for 0 ≤ i < [(n - 1)/2].

In this paper, crossed cubes are classified on the basis of their pancyclicity. Thus, G is called a pancyclic graph if G contains any cycle of length ℓ with L ≤ ℓ ≤ |V|, namely, if any cycle of length ℓ with L ≤ ℓ ≤ |V| can be embedded into G with dilation 1 for some constant positive integer L. G is called a node-pancyclic graph if for every node u and any integer ℓ ranging from a constant integer L to |V|, there exists a cycle C of length ℓ in G such that u is in C. Analogously, G is called an edge-pancyclic graph if, for every edge (u, v) and any integer ℓ ranging from a constant integer L to |V|, there exists a cycle C of length ℓ in G such that (u, v) is in C.

Proofs are presented in this paper for the following theorems relating to the node-pancyclicity and edge-pancyclicity of hypercubes and crossed cubes:

Theorem 1. If n ≥ 2 for any u ∈ V (CQ_n) and any integer ℓ with 4 ≤ ℓ ≤ 2ⁿ, there exists a cycle C of length ℓ in CQ_n such that u is in C.

Theorem 2. If n ≥ 2 for any u ∈ V (Q_n) and any even integer ℓ with 4 ≤ ℓ ≤ 2n, there exists a cycle C of length ℓ in Q_n such that u is in C.

Theorem 3. If n ≥ 2 for any (x, y) ∈ E(CQ_n) and any integer ℓ with 4 ≤ ℓ ≤ 2ⁿ, there exists a cycle C of length ℓ in CQ_n such that (x, y) is in C.

Theorem 4. If n ≥ 2 for any (x, y) ∈ E(Q_n) and any even integer ℓ with 4 ≤ ℓ ≤ 2ⁿ, there exists a cycle C of length ℓ in Q_n such that (x, y) is in C.

Note that the theorems for crossed cubes CQ_n and hypercubes Q_n are analogous, except that the cycles C in the crossed cubes CQ_n can be of either odd or even lengths, whereas the cycles C in the hypercubes Q_n can only be of even lengths.