All-fault-tolerant embedding of a complete binary tree in a group of Cayley graphs

This paper proposes an approach for embedding a complete binary tree with height k×(n-2^k+1)+(k-2)×2^k+1, where k=[log n], into an n-dimensional complete transposition graph (CT_n), star graph (ST_n), and bubblesort graph (BS_n) with dilations 1,3, and 2n-3 respectively. Furthermore, a fault-tolerant scheme is developed to recover multiple faults, and the dilations after recovery become at most 3,5, and 2n-1 for the CT_n, ST_n , and BS_n respectively