𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the shortness exponent of 1-tough, maximal planar graphs

✍ Scribed by Michal Tkáč

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
454 KB
Volume
154
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown that the shortness exponent of the class of l-tough, maximal planar graphs is at most log, 5. The non-Hamiltonian, l-tough, maximal planar graph with a minimum number of vertices is presented.

📜 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

An upper bound on the length of a Hamilt
An upper bound on the length of a Hamiltonian walk of a maximal planar graph
✍ Takao Asano; Takao Nishizeki; Takahiro Watanabe 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 840 KB

## 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 c