𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An upper bound on the shortness exponent of 1-tough, maximal planar graphs

✍ Scribed by Michael B. Dillencourt

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
292 KB
Volume
90
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

graphs is at most log, 6.

πŸ“œ SIMILAR VOLUMES

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.

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

New upper bounds on the decomposability
New upper bounds on the decomposability of planar graphs
✍ Fedor V. Fomin; Dimitrios M. Thilikos πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 335 KB πŸ‘ 1 views

## Abstract It is known that a planar graph on __n__ vertices has branch‐width/tree‐width bounded by $\alpha \sqrt {n}$. In many algorithmic applications, it is useful to have a small bound on the constant Ξ±. We give a proof of the best, so far, upper bound for the constant Ξ±. In particular, for th

Upper Bounds on the Maximal Number of Fa
Upper Bounds on the Maximal Number of Facets of 0/1-Polytopes
✍ TamΓ‘s Fleiner; Volker Kaibel; GΓΌnter Rote πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 157 KB

We prove two new upper bounds on the number of facets that a d-dimensional 0/1-polytope can have. The first one is 2(d -1)!+2(d -1) (which is the best one currently known for small dimensions), while the second one of O((d -2)!) is the best known bound for large dimensions.