##### On the galactic number of a hypercube

Review articleOpen access###### Michael Fellows - No affiliation found

**1988/01/01**DOI: 10.1016/0895-7177(88)90483-9

*Full-length article***Journal:**Mathematical and Computer Modelling

##### Abstract:

AbstractA 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-complete.

Request full text