首页   按字顺浏览 期刊浏览 卷期浏览 Hamiltonian cycles in planar triangulations with no separating triangles
Hamiltonian cycles in planar triangulations with no separating triangles

 

作者: Michael B. Dillencourt,  

 

期刊: Journal of Graph Theory  (WILEY Available online 1990)
卷期: Volume 14, issue 1  

页码: 31-49

 

ISSN:0364-9024

 

年代: 1990

 

DOI:10.1002/jgt.3190140105

 

出版商: Wiley Subscription Services, Inc., A Wiley Company

 

数据来源: WILEY

 

摘要:

AbstractA classical theorem of Hassler Whitney asserts that any maximal planar graph with no separating triangles is Hamiltonian. In this paper, we examine the problem of generalizing Whitney's theorem by relaxing the requirement that the triangulation be a maximal planar graph (i.e., that its outer boundary be a triangle) while maintaining the hypothesis that the triangulation have no separating triangles. It is shown that the conclusion of Whitney's theorem still holds if the chords satisfy a certain sparse‐ness condition and that a Hamiltonian cycle through a graph satisfying this condition can be found in linear time. Upper bounds on the shortness coefficient of triangulations without separating triangles are established. Several examples are given to show that the theorems presented here cannot be extended without strong additional hypotheses. In particular, a 1‐tough, non‐Hamiltonian triangulation with no separating triangles is pres

 

点击下载:  PDF (785KB)



返 回