The Characterizations of Hyper-Star Graphs Induced by Linearly Separable Boolean Functions

A hyper-star is a graph consisting of the union of some hypercubes with at least one common vertex. The graph induced by a linearly separable Boolean function is a hyper-star. We obtain some properties of hyper-stars and give a decomposition algorithm of a hyperstar. We give a determination condition for a hyper-star. The determination condition yields an algorithm of constructing all hyper-stars of n vertices in time O(n³).