𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Non-hamiltonian 54-tough maximal planar graphs

✍ Scribed by Jochen Harant; Peter J. Owens

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
194 KB
Volume
147
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

By a theorem of the toughness t(G) of a non-hamiitonian maximal planar graph G is less than or equal to 2. Improving a result of , it is shown that the shortness exponent of the class of maximal planar graphs with toughness greater than or equal to ~ is less than 1.

πŸ“œ SIMILAR VOLUMES

More than one tough chordal planar graph
More than one tough chordal planar graphs are Hamiltonian
✍ BοΏ½hme, Thomas; Harant, Jochen; TkοΏ½?, Michal πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 176 KB πŸ‘ 3 views

We prove the result stated in the title. Furthermore, it is proved that for any > 0, there is a 1-tough chordal planar graph G such that the length of a longest cycle of G is less than |V (G )|.

On the shortness exponent of 1-tough, ma
On the shortness exponent of 1-tough, maximal planar graphs
✍ Michal TkÑč πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 454 KB

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.

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