𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Improved Bounds for the Crossing Numbers of Km,n and Kn

✍ Scribed by de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R. B.; Salazar, G.

Book ID
118198909
Publisher
Society for Industrial and Applied Mathematics
Year
2006
Tongue
English
Weight
208 KB
Volume
20
Category
Article
ISSN
0895-4801

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the number of spanning trees of Kn an
On the number of spanning trees of Kn and Km, n
✍ Moh'd Z. Abu-Sbeih πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 170 KB

The object of this paper is to introduce a new technique for showing that the number of labelled spanning trees of the complete bipartite graph K,,,, is IT(m, n)l = m"-'n"-'. As an application, we use this technique to give a new proof of Cayley's formula IT(n)1 = nnm2, for the number of labelled s

An improvement of the crossing number bo
An improvement of the crossing number bound
✍ Bernard Montaron πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 194 KB

## Abstract The crossing number __cr__(__G__) of a simple graph __G__ with __n__ vertices and __m__ edges is the minimum number of edge crossings over all drawings of __G__ on the ℝ^2^ plane. The conjecture made by ErdΕ‘s in 1973 that __cr__(__G__) β‰₯ __Cm__^3^/__n__^2^ was proved in 1982 by Leighton

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