Diagonal Flips in Hamiltonian Triangulations on the Sphere

Ryuichi Mori; Atsuhiro Nakamoto; Katsuhiro Ota

doi:10.1007/s00373-002-0508-6

Diagonal Flips in Hamiltonian Triangulations on the Sphere

Ryuichi Mori, Atsuhiro Nakamoto, Katsuhiro Ota

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

24 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	413-418
Number of pages	6
Journal	Graphs and Combinatorics
Volume	19
Issue number	3
DOIs	https://doi.org/10.1007/s00373-002-0508-6
Publication status	Published - 2003 Nov 10

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-002-0508-6

Cite this

@article{918dde88c431445e87c5e20fc5fe54e9,

title = "Diagonal Flips in Hamiltonian Triangulations on the Sphere",

abstract = "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.",

author = "Ryuichi Mori and Atsuhiro Nakamoto and Katsuhiro Ota",

year = "2003",

month = nov,

day = "10",

doi = "10.1007/s00373-002-0508-6",

language = "English",

volume = "19",

pages = "413--418",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "3",

}

TY - JOUR

T1 - Diagonal Flips in Hamiltonian Triangulations on the Sphere

AU - Mori, Ryuichi

AU - Nakamoto, Atsuhiro

AU - Ota, Katsuhiro

PY - 2003/11/10

Y1 - 2003/11/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0242360740&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0242360740&partnerID=8YFLogxK

U2 - 10.1007/s00373-002-0508-6

DO - 10.1007/s00373-002-0508-6

M3 - Article

AN - SCOPUS:0242360740

SN - 0911-0119

VL - 19

SP - 413

EP - 418

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 3

ER -

Diagonal Flips in Hamiltonian Triangulations on the Sphere

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this