Let G=(V,E) be a graph of order n. A Hamiltonian cycle of G is a cycle that contains every vertex in G. Two Hamiltonian cycles C1= and C2= of G are independent if u1=v1 and ui ≠ vi for 2 ≤ i ≤ n. A set of Hamiltonian cycles {C1, C2, , Ck} of G is mutually independent if its elements are pairwise independent. The mutually independent hamiltonicity IHC(G) of a graph G is the maximum integer k such that for any vertex u of G there are k mutually independent Hamiltonian cycles of G starting at u. For the n-dimensional burnt pancake graph Bn, this paper proved that IHC(B2)=1 and IHC(Bn)=n for n ≥ 3.

In this paper, we propose an algorithm that solves the node-to-node disjoint paths problem in n-burnt pancake graphs in polynomial-order time of n. We also give a proof of its correctness as well as the estimates of time complexity O(n3) and the maximum path length 3n+4. We conducted a computer experiment for n=2 to 100 to measure the average performance of our algorithm. The results show that the average time complexity is O(n3.0) and the maximum path length is 3n+4.

A burnt pancake graph is a variant of Cayley graphs and its topology is suitable for massively parallel systems. However, for a burnt pancake graph, there is much room for further research. Hence, in this study, we focus on n-burnt pancake graphs and propose an algorithm to obtain n disjoint paths from a source node to n destination nodes in polynomial order time of n, n being the degree of the graph. In addition, we estimate the time complexity of the algorithm and the sum of path lengths. We also give a proof of correctness of the algorithm. Moreover, we report the results of computer simulation to evaluate the average performance of the algorithm.