Efficient proper embedding of a daisy cube
Abstract
For a set X of binary words of length h the daisy cube Qh(X) is defined as the subgraph of the hypercube Qh induced by the set of all vertices on shortest paths that connect vertices of X with the vertex 0h. 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 0h 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.
Keywords
DOI: https://doi.org/10.26493/1855-3974.2454.892
ISSN: 1855-3974
Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications