✦ LIBER ✦

Bounds for the crossing number of the N-cube

✍ Scribed by Tom Madej

Publisher: John Wiley and Sons
Year: 1991
Tongue: English
Weight: 658 KB
Volume: 15
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190150109

No coin nor oath required. For personal study only.

✦ Synopsis

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 and Guy and the lower bound is a significant improvement over what was previously known. Let N = 2^n^ be the number of vertices of Q~n~. We show that v(Q~n~) < 1/6__N__^2^. For the lower bound we prove that v(Q~n~) = Ω(N(lg N)^c lg lg N^), where c > 0 is a constant and lg is the logarithm base 2. The best lower bound using standard arguments is v(Q~n~) = Ω(N(lg N)^2^). The lower bound is obtained by constructing a large family of homeomorphs of a subcube with the property that no given pair of edges can appear in more than a constant number of the homeomorphs.

📜 SIMILAR VOLUMES

Bounds on the number of Hamiltonian circ

Bounds on the number of Hamiltonian circuits in the n-cube

✍ Robert James Douglas 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 224 KB

New upper anti lower ~,ounds arc found for the number of HamilI(,nian circuits in the graph of Ihe r -cube. (2) -1 i,, ,,' We show that h(n)~ [n(n -I)/212 .... '~'"""',"' = U~(e,) (3)

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

The crossing number of K1,3,n and K2,3,n

✍ Kouhei Asano 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 234 KB

In this article, we will determine the crossing number of the complete tripartite graphs K,.3.n and K2,3.n. Our proof depends on Kleitman's results for the complete bipartite graphs [D. J. Kleitman, The crossing number of K5,n. J. Combhatorial Theory 9 (1970) 375-3231. a graph G is the minimum numbe

Some Bounds for the Number of Blocks

✍ Ryuzaburou Noda 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 65 KB

Some natural upper bounds for the number of blocks are given. Only a few block sets achieving the bounds except trivial ones are known. Necessary conditions for the existence of such block sets are given.

A lower bound for the crossing number of

A lower bound for the crossing number of Cm × Cn

✍ Gelasio Salazar 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 67 KB 👁 3 views

The crossing number ofC5 �Cn

✍ Kle??, Mari�n; Richter, R. Bruce; Stobert, Ian 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 276 KB

We prove that the crossing number of C5 x C, is 372, which is consistent with the general conjecture that the crossing number of C,, x C, is ( m -2)n, for 3 5 m 5 n.