Abstract A graph $G=(V,E)$ is two-disjoint-cycle-cover $[r_1,r_2]$-pancyclic if for any integer $l$ satisfying $r_1 \leq l \leq r_2$, there exist two vertex-disjoint cycles $C_1$ and $C_2$ in $G$ such that the lengths of $C_1$ and $C_2$ are $l$ and $|V(G)| - l$, respectively, where $|V(G)|$ denotes the total number of vertices in $G$. On the basis of this definition, we further propose Ore-type conditions for graphs to be two-disjoint-cycle-cover vertex/edge $[r_1,r_2]$-pancyclic. In addition, we study cycle embedding in the $n$-dimensional locally twisted cube $LTQ_n$ under the consideration of two-disjoint-cycle-cover vertex/edge pancyclicity.

A graph G is pancyclic if it contains a cycle C of every length with 3≤l(C)≤∣V(G)∣⁠, where l(C) denotes the length of C and ∣V(G)∣ denotes the number of vertices in G. In this paper, we propose an augmented pancyclicity problem for the n-dimensional crossed cube CQn, which is a popular variant of the hypercube network. Let dC(u,v) denote the distance between any two distinct vertices u and v traversed by a cycle C in CQn, n≥4⁠. Then, for any integer m with ⌈n+12⌉+1≤m≤2n−1⁠, there exist cycles C of various lengths in CQn such that dC(u,v)=m⁠, where (i) 2m+1≤l(C)≤2n if n is odd and m=⌈n+12⌉+1 and (ii) 2m≤l(C)≤2n otherwise. This result indicates that any two distinct vertices of crossed cubes can be embedded on cycles of various feasible lengths with keeping any feasible distance from each other.

A tree T is labeled when the n vertices are distinguished from one another by names such as v/sub 1/, v/sub 2/...v/sub n/. Two labeled trees are considered to be distinct if they have different vertex labels even though they might be isomorphic. According to Cayley's tree formula, there are n/sup n-2/ labeled trees on n vertices. Prufer used a simple way to prove this formula and demonstrated that there exists a mapping between a labeled tree and a number sequence. From his proof, we can find a naive sequential algorithm which transfers a labeled tree to a number sequence and vice versa. However, it is hard to parallelize. In this paper, we shall propose an O(log n) time parallel algorithm for constructing a labeled tree by using O(n) processors and O(n log n) space on the EREW PRAM computational model.