In this paper, we show the explicit formula of the recurrence relation for the Tower of Hanoi on the star graph with four vertices, where the perfect tower of disks on a leaf vertex is transferred to the central vertex. This gives the solution to the problem posed at the 17th International Conference on Fibonacci Numbers and Their Applications[11]. Then, the recurrence relation are generalized to include the ones for the original 4-peg Tower of Hanoi and the Star Tower of Hanoi of transferring the tower from a leaf to another.