NUMBER OF HAMILTONIAN CYCLES IN A MAXIMAL PLANAR GRAPH

被引：18

作者：

HAKIMI, SL

SCHMEICHEL, EF

THOMASSEN, C

机构：

[1] AARHUS UNIV,DK-8000 AARHUS C,DENMARK

[2] CALIF STATE UNIV SAN JOSE,SAN JOSE,CA 95192

来源：

JOURNAL OF GRAPH THEORY | 1979年 / 3卷 / 04期

关键词：

D O I：

10.1002/jgt.3190030407

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on p vertices. In particular, we construct a p‐vertex maximal planar graph containing exactly four Hamiltonian cycles for every p ≥ 12. We also prove that every 4‐connected maximal planar graph on p vertices contains at least p/(log2 p) Hamiltonian cycles. Copyright © 1979 Wiley Periodicals, Inc., A Wiley Company

引用

页码：365 / 370

页数：6