Efficient proper embedding of a daisy cube

Abstract

For a set X of binary words of length h the daisy cube Q_h(X) is defined as the subgraph of the hypercube Q_h induced by the set of all vertices on shortest paths that connect vertices of X with the vertex 0^h. A vertex in the intersection of all of these paths is a minimal vertex of a daisy cube. A graph G isomorphic to a daisy cube admits several isometric embeddings into a hypercube. We show that an isometric embedding is proper if and only if the label 0^h is assigned to a minimal vertex of G. This result allows us to devise an algorithm which finds a proper embedding of a graph isomorphic to a daisy cube into a hypercube in linear time.