𝔖 Bobbio Scriptorium
✦   LIBER   ✦

New Lower Bounds for the Number of (≤ k)-Edges and the Rectilinear Crossing Number of Kn

✍ Scribed by Oswin Aichholzer; Jesus Garcia; David Orden; Pedro Ramos

Publisher
Springer
Year
2007
Tongue
English
Weight
213 KB
Volume
38
Category
Article
ISSN
0179-5376

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Bounds for the crossing number of the N-
Bounds for the crossing number of the N-cube
✍ Tom Madej 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 658 KB

## Abstract Let __Q__~__n__~ denote the n‐dimensional hypercube. In this paper we derive upper and lower bounds for the crossing number __v__(__Q__~__n__~), i.e., the minimum number of edge‐crossings in any planar drawing of __Q__~__n__~. The upper bound is close to a result conjectured by Eggleton

New bounds on the edge number of a k-map
New bounds on the edge number of a k-map graph
✍ Zhi-Zhong Chen 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 310 KB 👁 1 views

## Abstract It is known that for every integer __k__ ≥ 4, each __k__‐map graph with __n__ vertices has at most __kn__ − 2__k__ edges. Previously, it was open whether this bound is tight or not. We show that this bound is tight for __k__ = 4, 5. We also show that this bound is not tight for large en