𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An improved upper bound on the crossing number of the hypercube

✍ Scribed by Luerbio Faria; Celina Miraglia Herrera de Figueiredo; Ondrej Sýkora; Imrich Vrt'o

Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
288 KB
Volume
59
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We draw the n‐dimensional hypercube in the plane with ${5\over 32}4^{n}-\lfloor{{{{n}^{2}+1}\over 2}}\rfloor {2}^{n-2}$ crossings, which improves the previous best estimation and coincides with the long conjectured upper bound of Erdös and Guy. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 145–161, 2008

📜 SIMILAR VOLUMES

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

An Upper Bound for the Independent Domin
An Upper Bound for the Independent Domination Number
✍ Liang Sun; Jianfang Wang 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 87 KB

Let G be a simple graph of order n and minimum degree $. The independent domination number i(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. In this paper, we show that i(G) n+2$&2 -n$. Thus a conjecture of Favaron is settled in the affirmative.

An improved edge bound on the interval n
An improved edge bound on the interval number of a graph
✍ Jeremy R. Spinrad; G. Vijayan; Douglas B. West 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB 👁 2 views

The upper bound on the interval number of a graph in terms of its number of edges is improved. Also, the interval number of graphs in hereditary classes is bounded in terms of the vertex degrees. A representation of a graph as an intersection graph assigns each vertex a set such that vertices are a

On an upper bound for the harmonious chr
On an upper bound for the harmonious chromatic number of a graph
✍ Zhikang Lu 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

## Abstract The upper bound for the harmonious chromatic number of a graph that has been given by Sin‐Min Lee and John Mitchem is improved.

On the Achromatic Number of Hypercubes
On the Achromatic Number of Hypercubes
✍ Yuval Roichman 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 96 KB

The achromatic number of a finite graph G, (G), is the maximum number of independent sets into which the vertex set may be partitioned, so that between any two parts there is at least one edge. For an m-dimensional hypercube P m 2 we prove that there exist constants 0<c 1 <c 2 , independent of m, su