On the number of hamiltonian cycles in a maximal planar graph | Zendy

Hakimi S. L. | Zendy; Schmeichel E. F. | Zendy; Thomassen C. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

On the number of hamiltonian cycles in a maximal planar graph

Author(s) -

Hakimi S. L.,

Schmeichel E. F.,

Thomassen C.

Publication year - 1979

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.3190030407

Subject(s) - mathematics , combinatorics , planar graph , wheel graph , hamiltonian path , quartic graph , planar , hamiltonian (control theory) , graph , hamiltonian path problem , vertex (graph theory) , graph power , discrete mathematics , outerplanar graph , line graph , voltage graph , computer science , mathematical optimization , computer graphics (images)

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 /(log 2 p ) Hamiltonian cycles.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research