Efficient proper embedding of a daisy cube

Authors

DOI:

https://doi.org/10.26493/1855-3974.2454.892

Keywords:

Daisy cube, partial cube, isometric embedding, proper embedding

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.

Published

2021-10-25

Issue

Section

Articles