A Hamiltonian walk of a connected graph is a shortest closed walk that passes through every vertex at least once, and the length of a Hamiltonian walk is the total number of edges traversed by the walk. We show that every maximal planar graph with p(≥ 3) vertices has a Hamiltonian cycle or a Hamiltonian walk of length ≤ 3(p ‐ 3)/2.
ASJC Scopus subject areas
- Geometry and Topology
- Discrete Mathematics and Combinatorics