✦ LIBER ✦

On the galactic number of a hypercube

✍ Scribed by Michael Fellows; Mark Hoover; Frank Harary

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 298 KB
Volume: 11
Category: Article
ISSN: 0895-7177
DOI: 10.1016/0895-7177(88)90483-9

No coin nor oath required. For personal study only.

✦ Synopsis

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 determining the galactic number of a graph is shown to be NP-comphte.

📜 SIMILAR VOLUMES

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

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

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 spanning trees of the gene

The number of spanning trees of the generalized hypercube network

✍ C.S. Yang; L.C. Han 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 663 KB

On a leverage problem in the hypercube

✍ Peter Hamburger; Raymond E. Pippert; W. Douglas Weakley 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 210 KB

On the area of hypercube layouts

✍ Ronald I. Greenberg; Lee Guan 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 106 KB

This paper precisely analyzes the wire density and required area in standard layout styles for the hypercube. It shows that the most natural, regular layout of a hypercube of N 2 nodes in the plane, in an N × N grid arrangement, uses 2N/3 + 1 horizontal wiring tracks for each row of nodes. (In the p