𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the queue-number of the hypercube

✍ Scribed by Petr Gregor; Riste Škrekovski; Vida Vukašinović

Book ID
119236589
Publisher
Elsevier Science
Year
2011
Tongue
English
Weight
180 KB
Volume
38
Category
Article
ISSN
1571-0653

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

On the galactic number of a hypercube
On the galactic number of a hypercube
✍ Michael Fellows; Mark Hoover; Frank Harary 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 298 KB

A galaxy is a union of vertex disjoint stars. The galactic number of a graph is the minimum number of galaxies which partition the edge set. The galactic number of complete graphs is determined. This result is used to give bounds on the galactic number of binary cube graphs. The problem of determini

An improved upper bound on the crossing
An improved upper bound on the crossing number of the hypercube
✍ Luerbio Faria; Celina Miraglia Herrera de Figueiredo; Ondrej Sýkora; Imrich Vrt' 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB

## 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

The number of perfect matchings in a hyp
The number of perfect matchings in a hypercube
✍ Niall Graham; Frank Harary 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 243 KB

A perfect matching or a l-factor of a graph G is a spanning subgraph that is regular of degree one. Hence a perfect matching is a set of independent edges which matches all the nodes of G in pairs. Thus in a hypercube parallel processor, the number of perfect matchings evaluates the number of diff