Diagonal flips in Hamiltonian triangulations on the sphere

被引：21

作者：

Mori, R

Nakamoto, A

Ota, K

机构：

[1] Yokohama Natl Univ, Dept Math, Hodogaya Ku, Yokohama, Kanagawa 2408501, Japan

[2] Keio Univ, Dept Math, Kohoku Ku, Yokohama, Kanagawa 2238522, Japan

来源：

GRAPHS AND COMBINATORICS | 2003年 / 19卷 / 03期

关键词：

Hamilton Cycle; Hamiltonian Triangulation;

D O I：

10.1007/s00373-002-0508-6

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper, we shall prove that any two Hamiltonian triangulations on the sphere with n greater than or equal to 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.

引用

页码：413 / 418

页数：6