In this paper, we shall prove that any two Hamiltonian triangulations on the sphere with n ≥ 5 vertices can be transformed into each other by at most 4n - 20 diagonal flips, preserving the existence of Hamilton cycles. Moreover, using this result, we shall prove that at most 6n - 30 diagonal flips are needed for any two triangulations on the sphere with n vertices to transform into each other.
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics