Abstract Two vertices $u$ and $v$ in a graph $G=(V,E)$ are in the same orbit if there exists an automorphism $\phi $ of $G$ such that $\phi (u)=v$. The orbit number of a graph $G$, denoted by $Orb(G)$, is the smallest number of orbits, which form a partition of $V(G)$, in $G$. All vertex-transitive graphs $G$ are with $Orb(G)=1$. Since the $n$-dimensional hypercube, denoted by $Q_{n}$, is vertex-transitive, it follows that $Orb(Q_{n})=1$ for $n\geq 1$. Pai, Chang, and Yang proved that the $n$-dimensional folded crossed cube, denoted by $FCQ_{n}$, is vertex-transitive if and only if $n\in \{1,2,4\}$, namely $Orb(FCQ_{1})=Orb(FCQ_{2})=Orb(FCQ_{4})=1$. In this paper, we prove that $Orb(FCQ_{n})=2^{\lceil \frac{n}{2}\rceil -2}$ if $n\geq 6$ is even and $Orb(FCQ_{n}) = 2^{\lceil \frac{n}{2}\rceil -1}$ if $n\geq 3$ is odd.

Let |$S$| be a subset of vertices of a graph |$G=(V,E)$|⁠. Let |$N[v]$| denote the set of closed neighbors of vertex |$v$|⁠. An attack |${\mathcal A}$| on |$S$| is a set of disjoint vertex sets |$\{A_v\,|\,A_v\subseteq N[v]{\setminus } S,\ v\in S\}$|⁠, and a defense |${\mathcal D}$| on |$S$| is a set of disjoint vertex sets |$\{D_v\,|\,D_v\subseteq N[v]\cap S,\ v\in S\}$|⁠. A set |$S$| is secure if for any attack |${\mathcal A}$| to |$S$|⁠, there exists a defense |${\mathcal D}$| on |$S$| such that |$|D_v|\geq |A_v|$| for all |$v$| in |$S$|⁠. A secure set |$S$| of |$G$| is called a global secure set of |$G$| if every vertex in |$V{\setminus } S$| is adjacent to at least one member of |$S$|⁠. The global security problem is to find a minimum global secure set of |$G$|⁠. In this paper, we propose an |$O(|V|\log \Delta )$|-time algorithm for finding the cardinality of a minimum global secure set on trees where |$\Delta $| is the maximum degree of the tree.

Given two strings X and Y and a constraining string P, a string Z is called a constrained longest common subsequence of X and Y with respect to P if Z is the longest common subsequence of X and Y such that P is a subsequence of Z. In this paper, we propose an O(r×min{mN, nM})-time algorithm for solving this problem, where m, n and r are the lengths of X, Y and P, respectively, and M and N are the number of runs of the run-length-encoded strings of X and Y, respectively.

In this paper, we define a new subclass of integer linear programming problems called the composition problem. We shall propose efficient algorithms for solving this problem and its variants. Moreover, as an application of the composition problem, those algorithms are applied to solve the P-constrained secure set problem, which is a variation of the secure set problem introduced in [5], on trees. A P-constrained secure set problem is to find a minimum secure set containing a set of |P| predetermined vertices.

A rotation in a binary tree is a local restructuring that changes the tree into another and preserves the inorder sequence. The rotation distance between two binary trees is the minimum number of rotations needed to transform one into another. However, a polynomial-time algorithm for computing rotation distances between any two binary trees has still not been found. Lucas (The Computer Journal, 47, 259–269, 2004) recently presented an O(n2)-time algorithm for finding the exact rotation distance between two binary trees that are of a restricted form (each node has at most one child in the source tree and there is at most one zig-zag pair in the destination tree), where n is the number of nodes in each binary tree. In this paper, by using the coding technique of left weight sequences, which was proposed by Pallo (The Computer Journal, 9, 171–175, 1986), we find another restricted set of binary trees in which any two of them can be transformed with the exact rotation distance. Our algorithm can be performed in linear time for finding the rotation distance between any two trees in the restricted set. Moreover, the actual sequence of transforming rotations can also be built.

There are various ways to measure the shape difference between two n-node rooted binary trees (binary trees for short). A rotation on a binary tree is a local restructuring that changes the tree into another one preserving the in-order sequence. The rotation distance between two binary trees is the minimum number of rotations needed to transform one into another. Till now, no polynomial–time algorithm exists for computing the rotation distance between any two binary trees. Recently, Lucas (Comput. J., 47, 259–269, 2004) presented an O(n2)–time algorithm for finding the rotation distance between two binary trees, where the source tree is a degenerate tree and the destination tree is an angle tree. This paper improves the time-complexity to O(n) under this constraint.