On the galactic number of a hypercube
Review articleOpen access
1988/01/01 Full-length article DOI: 10.1016/0895-7177(88)90483-9
Journal: Mathematical and Computer Modelling
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