An upper bound on the length of a Hamiltonian walk of a maximal planar graph
Authors:
- 1 September 1980
- journal article
- Published by Wiley in Journal of Graph Theory
- Vol. 4 (3) , 315-336
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.Keywords
This publication has 6 references indexed in Scilit:
- On Hamiltonian Walks in GraphsSIAM Journal on Computing, 1974
- Shortness exponents of families of graphsJournal of Combinatorial Theory, Series A, 1973
- Hamiltonian circuits on 3-polytopesJournal of Combinatorial Theory, 1970
- GRAPH THEORY1969
- Simple paths on polyhedraPacific Journal of Mathematics, 1963
- A Theorem on GraphsAnnals of Mathematics, 1931