Efficient proper embedding of a daisy cube

Aleksander Vesel

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


Daisy cube, partial cube, isometric embedding, proper embedding

Full Text:

MANUSCRIPT


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