Efficient proper embedding of a daisy cube
DOI:
https://doi.org/10.26493/1855-3974.2454.892Keywords:
Daisy cube, partial cube, isometric embedding, proper embeddingAbstract
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.
Downloads
Published
Issue
Section
License
Articles in this journal are published under Creative Commons Attribution 4.0 International License
https://creativecommons.org/licenses/by/4.0/