论文标题
有效地正确嵌入雏菊立方体
Efficient proper embedding of a daisy cube
论文作者
论文摘要
对于一套$ x $的二进制单词$ h $的二进制单词daisy cube $ q_h（x）$定义为由所有顶点引起的HyperCube $ Q_H $的子图，这些顶点在最短路径上将$ x $的顶点与顶点$ 0 ^h $连接的最短路径连接起来。所有这些路径交集中的顶点是雏菊立方体的最小顶点。 Daisy Cube的图$ G $同构将几个等轴测嵌入到HyperCube中。我们证明，仅当标签$ 0 ^h $分配给$ g $的最小顶点时，等距嵌入是正确的。该结果使我们能够设计出一种算法，该算法在线性时间以线性时间将图形同构的正确嵌入到雏菊立方体中。
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.
