BranchesHistoryHelpLogin
Welcome guest
You're not logged in.
278 users online, thereof 0 logged in

Theorem: Characterization of Planar Hamiltonian Graphs

(Note that finding a Hamiltonian cycle is an NP-hard problem and there is much research going on to find theoretical results about finding not only necessary but also sufficient criteria for a graph to be Hamiltonian. The following theorem is one such research1591 result providing a necessary and sufficient criterion for a planar graph to be Hamiltonian. The theorem is also the main motivation of the concept of minimal tree decomposability \(\tau(G)\) of a graph \(G\).)

For all simple planar graphs \(G\), the following equivalence holds: \(G\) is Hamiltonian, if and only if the minimal tree decomposability of every of its dual graphs equals \(2\), formally:

\[\text{Simple and planar }G:~G\text{ is Hamiltonian}\quad\Longleftrightarrow\quad \tau(G^*)=2\text{ for all dual graphs }G^*\text{ of }G.\]

Example

The idea for this equivalence is illustrated in the following example:

| | | | | created: 2017-01-19 16:43:36 | modified: 2018-05-10 15:17:22 | by: bookofproofs | references: [1591]

1.Proof: (related to "Characterization of Planar Hamiltonian Graphs")

Edit or AddNotationAxiomatic Method

This work was contributed under CC BY-SA 4.0 by:

This work is a derivative of:

(none)

Bibliography (further reading)

[1591] Piotrowski, Andreas: “bookofproofs.org”, Own Work, 2014