On the Hamiltonian Number of a Planar Graph

2015/08/27 by Thomas M. Lewis, Lewis, Thomas M.
Mathematics · #05C10 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C10

paper · pdf · doi:10.48550/arxiv.1508.06892

11 pages

arxiv created 2015/08/27 · arxiv updated 2015/08/28

Abstract

The Hamiltonian number of a connected graph is the minimum of the lengths of the closed, spanning walks in the graph. In 1968, Grinberg published a necessary condition for the existence of a Hamiltonian cycle in a planar graph, formulated in terms of the lengths of its face cycles. We show how Grinberg's theorem can be adapted to provide a lower bound on the Hamiltonian number of a planar graph.

Related

• A note on the Grinberg condition in the cycle spaces
• Every 2-connected, cubic, planar graph with faces of size at most 6 is Hamiltonian
• Are highly connected 1-planar graphs Hamiltonian?
• A Size Bound for Hamilton Cycles
• Large cycles in essentially 4-connected graphs