An upper bound on the length of a Hamiltonian walk of a maximal planar graph
Takao Asano, Takao Nishizeki, Takahiro Watanabe · Journal of Graph Theory · 1980
Abstract 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.