𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An upper bound on the length of a Hamiltonian walk of a maximal planar graph

✍ Scribed by Takao Asano; Takao Nishizeki; Takahiro Watanabe

Publisher
John Wiley and Sons
Year
1980
Tongue
English
Weight
840 KB
Volume
4
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

On the number of hamiltonian cycles in a
On the number of hamiltonian cycles in a maximal planar graph
✍ S. L. Hakimi; E. F. Schmeichel; C. Thomassen πŸ“‚ Article πŸ“… 1979 πŸ› John Wiley and Sons 🌐 English βš– 243 KB πŸ‘ 2 views

## Abstract We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on __p__ vertices. In particular, we construct a __p__‐vertex maximal planar graph containing exactly four Hamiltonian cycles for every __p__ β‰₯ 12. We also pro

On the number of cycles of length 4 in a
On the number of cycles of length 4 in a maximal planar graph
✍ Ahmad Fawzi Alameddine πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 148 KB πŸ‘ 2 views

## Abstract Let __p__ and __C__~4~ (__G__) be the number of vertices and the number of 4‐cycles of a maximal planar graph __G__, respectively. Hakimi and Schmeichel characterized those graphs __G__ for which __C__~4~ (__G__) = 1/2(__p__^2^ + 3__p__ ‐ 22). This characterization is correct if __p__ β‰₯

On the number of cycles of length k in a
On the number of cycles of length k in a maximal planar graph
✍ S. L. Hakimi; E. F. Schmeichel πŸ“‚ Article πŸ“… 1979 πŸ› John Wiley and Sons 🌐 English βš– 723 KB

Let G be a maximal planar graph with p vertices, and let Ck(G) denote the number of cycles of length k in G. We first present tight bounds for C,(G) and C,(G) in terms of p. We then give bounds for Ck(G) when 5 5 k 5 p , and consider in particular bounds for C,(G), in terms of p. Some conjectures an