ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 21 (2021) #P2.07 / 271–282
https://doi.org/10.26493/1855-3974.2454.892
(Also available at http://amc-journal.eu)
Efficient proper embedding of a daisy cube*
Aleksander Vesel
Faculty of Natural Sciences and Mathematics, University of Maribor,
SI-2000 Maribor, Slovenia
Received 4 October 2020, accepted 14 June 2021, published online 25 October 2021
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.
Math. Subj. Class. (2020): 05C12, 05C85
1 Introduction
Hypercube is one of the most important interconnection scheme for multicomputers. An
obstacle to a direct application of a hypercube is the fact that the number of different hy-
percubes is very small with respect to the wanted (maximum) number of nodes, that is to
say, the number of vertices of a hypercube is always equal to a power of two. For that
reason, several other interconnection topologies for multicomputers based on hypercubes
have been proposed. These graphs have been devised to preserve a hypercube’s most essen-
tial properties while allowing more variety of resulting specific graphs. The corresponding
families of graphs are mostly various subgraphs of a hypercube, of which its isometric sub-
graphs, i.e. its induced subgraphs that preserve distances, are of particular importance. A
crucial problem in this scope is to find an embedding of a graph of this type to a hypercube
(see for example [1, 4, 16]).
*This work was supported by the Slovenian Research Agency under the grants P1-0297, J1-2452, J1-9109 and
J1-1693.
E-mail address: aleksander.vesel@um.si (Aleksander Vesel)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
272 Ars Math. Contemp. 21 (2021) #P2.07 / 271–282
Quite recently, a new concept which led to the class of graphs called daisy cubes has
been proposed in [9]. It has been shown that daisy cubes are isometric subgraphs of a
hypercube, moreover, they include several other important classes of graphs, some well-
known examples are Fibonacci and Lucas cubes (see, for example [2, 5, 8, 11]) as well
as some other families of generalized Fibonacci cubes and generalized Lucas cubes [3, 6,
7, 15]. Daisy cubes play an essential role in showing that specific generalized Fibonacci
cubes’ cube-complements are isometric subgraphs of a hypercube [13]. It is also proven
that a class of graphs, which is of significant importance in chemical graph theory, also
belongs to daisy cubes [14].
In [12], daisy cubes are characterized in terms of an expansion procedure. For a given
graph G isomorphic to a daisy cube, but without the corresponding embedding into a hy-
percube, an algorithm which finds a proper embedding of G into a hypercube in O(mn)
time is also presented.
Several challenging open problems concerning daisy cubes have been proposed [9, 12].
In this paper, we focus our study to the following one.
Problem 1.1. Is there a faster way of finding the vertex 0h of a daisy cube Qh(X) than the
one provided in [12]?
It is also noted that a positive answer to Problem 1 would give a linear time algorithm
for finding a proper embedding of a graph isomorphic to a daisy cube.
The paper is organized as follows. In the next section some basic definitions, concepts
and results needed in the sequel are given. In Section 3, a notion of a minimal vertex of a
daisy cube is introduced. Some necessary and sufficient conditions that a minimal vertex
has to fulfill are also given. In Section 4, it is shown that an isometric embedding of a graph
isomorphic to a daisy cube, but without the corresponding embedding into a hypercube, can
be constructed in linear time even if a minimal vertex of a daisy cube is unknown. The last
section shows that an isometric embedding devised in the Section 4 can be applied in order
to find a proper embedding within the same time bound.
2 Preliminaries
Let B = {0, 1}. If b is a word of length h over B, that is, b = (b1, . . . , bh) ∈ Bh, then we
will briefly write b as b1 . . . bh. If x, y ∈ Bh, then the Hamming distance H(x, y) between
x and y is the number of positions in which x and y differ.
We will use [n] for the set {1, 2, . . . , n}.
The hypercube of order h or simply h-cube, denoted by Qh, is the graph G = (V,E)
where the vertex set V (G) is the set of all binary strings b = b1b2 . . . bh, bi ∈ {0, 1} for
all i ∈ [h], and two vertices x, y ∈ V (G) are adjacent in Qh if and only if the Hamming
distance between x and y is equal to one.
For a binary string b = b1b2 . . . bn, let bi = 1 − bi for i ∈ [h]. The weight of u ∈ Bh
is w(u) =
∑h
i=1 ui, in other words, w(u) is the number of 1s in the word u. For the
concatenation of bits the power notation will be used, for instance 0h = 0 . . . 0 ∈ Bh.
If G is a connected graph, then the distance dG(u, v) (or simply d(u, v)) between ver-
tices u and v is the length of a shortest u, v-path (that is, a shortest path between u and v)
in G. The set of vertices lying on all shortest u, v-paths is called the interval between u
and v and denoted by IG(u, v) [10]. We will also write I(u, v) when G will be clear from
the context.
A. Vesel: Efficient proper embedding of a daisy cube 273
If G is a graph and X ⊆ V (G), then G[X] denotes the subgraph of G induced by X .
If u is a vertex of a graph G, let N(u) denote the set of neighbors of u. Moreover, let
N [u] = N(u) ∪ {u}.
Let G = (V,E) be a graph. A mapping α : V (G) → V (Qh) is an isometric embedding
of G into Qh if dQh(α(u), α(v)) = dG(u, v) for every u, v ∈ V (G). If u ∈ V (G), we will
denote the i-th coordinate of α(u) as α(i)(u).
Let G be a connected graph. The isometric dimension of G is the smallest integer h
such that G admits an isometric embedding into Qh. Isometric subgraphs of hypercubes
are called partial cubes.
Let ≤ be the partial order on V (Qh) defined with u1 . . . uh ≤ v1 . . . vh if ui ≤ vi holds
for all i ∈ [h]. For X ⊆ V (Qh) the graph induced by the set {v ∈ V (Qh) | v ≤ x for some
x ∈ X} is a daisy cube of Qh generated by X and denoted by Qh(X).
Let also ∨, ∧ and ⊕ denote the bitwise OR, bitwise AND and bitwise exclusive OR
operator, respectively.
By a slight abuse of definition, we will say that a graph G is a daisy cube if it is
isomorphic to a daisy cube generated by some X ⊆ V (Qh). If G is a daisy cube Qh(X),
then G may admit more than one isometric embedding of G into the h-cube. Let XG ⊆ Bh
be the set of labels of the vertices of G assigned by an isometric embedding α, i.e. XG =
α(V (G)). We say that α is a proper embedding of G if G is isomorphic to Qh(XG).
Let G be a graph isomorphic to a daisy cube of Gh and let α denote a proper embedding.
Note that every permutation of indices of α yields basically the “same” embedding. We
say that proper embeddings α and β are equivalent if β can be obtained from α by a
permutation of its indices.
For a daisy cube Qh(X), let X̂ denote the antichain consisting of the maximal elements
of the poset (X,≤). It was shown in [9] that Qh(X) = Qh(X̂). Hence, for a given set
X ⊆ Bn it is enough to consider the antichain X̂ . The vertices of Qh(X) from X̂ are
called the maximal vertices of Qh(X). More generally, if G is a daisy cube of Qh with a
proper embedding α such that α(v) = 0h, then X ⊆ V (G) is the set of maximal vertices
of G with respect to v if G ∼= Qh(α(X)) and α̂(X) = α(X). Moreover, v is the minimal
vertex of G with respect to α. We also say that v is a minimal vertex of G if there exists a
proper embedding α such that α(v) = 0h.
The following result shows that a daisy cube is a subgraph of Qh induced by the union
of intervals between 0h and the vertices from X̂ [9].
Lemma 2.1. Let X ⊆ Bh. Then Qh(X) = Qh[∪x∈X̂I(0
h, x)].
3 Minimal vertices of a daisy cube
If u ∈ V (Qh(X)), then I(0n, u) induces a w(u)-cube in Qh(X). Note that if x ∈ X̂ , then
the cube induced by I(0n, x) is maximal in Qh(X), i.e., it is not contained in any other
cube that belongs to Qh(X).
If x ∈ Bh, let Sx denote the set of indices of v with xi = 1, i.e., Sx = {i |xi =
1 and i ∈ [h]}.
Let v ∈ Bh and let vβ : Bh → Bh be the function defined as
vβ(i)(u) =
{
ui, vi = 0
ūi, vi = 1
274 Ars Math. Contemp. 21 (2021) #P2.07 / 271–282
Lemma 3.1. Let G be a graph isomorphic to a daisy cube of Qh with a proper em-
bedding α such that α(v0) = 0h and X̂ ⊆ V (G) is its corresponding maximal set. If
v ∈ ∩x∈X̂I(v
0, x), then
(i) vβ restricted to α(V (G)) is a bijection that maps to α(V (G)),
(ii) vβ ◦ α is a proper embedding of G with the minimal vertex v and the maximal vertex
set Y = {y | vβ(α(y)) = α(x) and x ∈ X̂}.
Proof. (i) We have to show that if v ∈ ∩x∈X̂I(v
0, x), then for every u ∈ α(V (G))) there
is exactly one vβ(u) ∈ α(V (G)). Note that α−1(u) ∈ I(v0, x) and v ∈ I(v0, x) for some
x ∈ X̂ . Thus, Su ⊆ Sα(x) and Sα(v) ⊆ Sα(x). It follows that Svβ(u) ⊆ Sα(x). Since α is
proper, α(V (G)) = ∪x∈X̂I(0
h, α(x)) by Lemma 2.1 and we obtain vβ(u) ∈ V (α(G)).
In order to see that vβ is injective, note that vβ(vβ(u)) = u for every u ∈ α(V (G)).
Suppose to the contrary that there exist u, z ∈ α(V (G)), u ̸= z, such that vβ(u) =v β(z).
It follows that vβ(vβ(u)) =vβ(vβ(z)) and thus u = z, which yields a contradiction.
(ii) By (i), vβ maps from α(V (G)) to α(V (G)). Let x ∈ X̂ and recall that vβ(vβ(α(x))) =
α(x). Thus, if y ∈ V (G) such that α(y) = vβ(α(x)), we have vβ(α(y)) = α(x). More-
over, vβ(v) = 0h. It follows that Y = {y | vβ(α(y)) = α(x) and x ∈ X̂} is the maximal
vertex set of G with respect to vβ ◦ α, while v is the corresponding minimal vertex.
00000
00011
00100 00111
01000 01011
00001
0001000010 0000110000 10011
10010 10001
10011 1000001011 0100000111 00100
10001 1001000011 0000001001 0101001010 0100100101 0011000110 00101
x
x’
v
v
3
0
y
y’ z’
z
Figure 1: Two proper embeddings of a daisy cube.
Figure 1 shows two proper embeddings of a daisy cube G. The embedding on the left
hand side, say α, admits the set of maximal vertices X̂ = {x, y, z} with labels α(x) =
10011, α(y) = 01011 and α(z) = 00111. Let v0 ∈ V (G) such that v0 = α−1(00000).
Then I(v0, x) ∩ I(v0, y) ∩ I(v0, z) = {v0, v1, v2, v3}, where α(v3) = 00011. The em-
bedding on the right hand side of Figure 1 is v
3
β ◦ α with the set of maximal vertices
Y = {x′, y′, z′}, where the corresponding labels are α(x′) = 10000, α(y′) = 01000
and α(z′) = 00100. Note also that v
3
β(α(x′)) = 10011, v
3
β(α(y′)) = 01011 and
v3β(α(z′)) = 00111.
Let u ∈ V (G) where G = Qh(X) and let Xu be the maximal subset of X̂ with the
property u ∈ ∩x∈XuI(0h, x). Let Gu be the graph induced by the set ∪x∈XuI(0h, x), i.e.
Gu = G[∪x∈XuI(0h, x)]. Note that by Lemma 3.1 and Lemma 2.1, Gu is a daisy cube of
A. Vesel: Efficient proper embedding of a daisy cube 275
Qh and u is its minimal vertex. Observe for example the graph Q4(0111, 1011, 1101, 1110)
on the right hand side of Figure 2: if u = 1100, then Xu = {1110, 1101}.
As noted in [12], an efficient way of finding a minimal vertex of a daisy cube G would
give a linear time algorithm for finding a proper embedding of G. It was also shown that
if G is a daisy cube of Qh, then a minimal vertex of G is of degree h. It is not difficult to
see that a vertex of degree h need not to be a minimal vertex of G. Note for example that
Q−h (that is a vertex deleted Qh) admits 2
h − h − 1 vertices of degree h and exactly one
minimal vertex (see also Figure 2, where Q−4 is depicted).
Proposition 3.2. Let u ∈ V (G), where G = Qh(X) and d(u) = h . Moreover, let Xu be
the maximal subset of X̂ such that u ∈ ∩x∈XuI(0h, x). Then for every proper embedding
α, the minimal vertex of G with respect to α belongs to ∩x∈XuI(0h, x).
Proof. Let v be the minimal vertex of G with respect to some proper embedding. Note that
for every x ∈ X̂ and every u ∈ I(0h, x) we have d(v, u) ≤ |Sx|. Suppose to the contrary
that v ̸∈ ∩x∈XuI(0h, x). It follows that there exists x ∈ Xu such that v ̸∈ I(0h, x). Since
u ∈ I(0h, x), it follows that Su ⊆ Sx. Moreover, since v ̸∈ I(0h, x), there exists an index
j ̸∈ Sx such that vj = 1. It follows that the string u defined by
ui =
{
v̄i, i ∈ Sx
0, otherwise
is a vertex of I(0h, x) with d(v, u) > |Sx| and we obtain a contradiction.
Theorem 3.3. If G = Qh(X) and x̂ = ∧x∈X̂x, then for every proper embedding α, v is
the minimal vertex of G with respect to α if and only if v ∈ ∩x∈X̂I(0
h, x) = I(0h, x̂).
Proof. By Lemma 3.1 and Proposition 3.2, v is a minimal vertex of G, if and only if
v ∈ ∩x∈X̂I(0
h, x). Note that v ∈ ∩x∈X̂I(0
h, x) if and only if Sv ⊆ ∩x∈XSx. Since
Sx̂ = ∩x∈XSx, for every v ∈ V (G) we have v ∈ ∩x∈X̂I(0
h, x) if and only if v ≤ x̂. It
follows that ∩x∈XI(0h, x) = I(0h, x̂) and the assertion follows.
4 Isometric embedding
If v is a vertex of a partial cube G, then NvG(u) (or simply N
v(u) ) is the set of neighbors
of u which are closer to v than u, more formally NvG(u) := {z | z ∈ N(u) and d(v, z) =
d(v, u)− 1},
If G is a graph isomorphic to a hypercube (but without an embedding), then its isometric
embedding is easy to obtain as shown in the next result.
Proposition 4.1. Let G be a graph isomorphic to a h-cube, v an arbitrary vertex of G and
α : V (G) → V (Qh) a function such that α(v) = 0d, the vertices of N(v) obtain pairwise
different labels of the form 0i−110h−i, i ∈ [h], while for the other vertices u ∈ V (G)
ordered by an increasing distance from v, we set α(u) = ∨z∈Nv(u)α(z). Then α is an
isometric embedding of G into Qh. Moreover, when a labeling of vertices in N [v] is chosen,
α is unique.
Proof. Since a hypercube is vertex-transitive, we may choose an arbitrary vertex v of G
and set α(v) = 0h. Moreover, for every u ∈ V (G) with d(v, u) = s, s ≥ 1, we must have
Nv(u) = {z | α(i)(z) = α(i)(u) = 1 for exactly one i ∈ [h] and α(j)(z) = α(j)(u) for
276 Ars Math. Contemp. 21 (2021) #P2.07 / 271–282
every j ∈ [h] \ {i}}. Thus, α(u) = ∨z∈Nv(u)α(z). It follows that for chosen labeling of
vertices in N [v], α is unique.
Lemma 4.2. Let G be partial cube of isometric dimension h, u a vertex of degree h in
G and let for every v ∈ V (G) \ N [u] it holds that |Nu(v)| ≥ 2. Define the function
α : V (G) → V (Qh) such that α(u) = 0h, the vertices of N(u) obtain pairwise different
labels of the form 0i−110h−i, i ∈ [h], while for the other vertices v ∈ V (G) ordered by an
increasing distance from u, we set α(v) = ∨z∈Nu(v)α(z). Moreover,
(i) α is an isometric embedding of G into Qh,
(ii) when a fixed embedding of vertices in N [v] is chosen, α is unique.
Proof. Since G is a partial cube of dimension h, we may assume that G is an isometric
subgraph of an (unlabeled) h-cube H . Let β be an embedding of H with respect to v as
defined in Proposition 4.1 and let α be an embedding of G such that for every z ∈ N [u] we
set α(z) = β(z). Since |NuG(v)| ≥ 2 and NuG(v) ⊆ NuH(v) for every v ∈ V (G) \N [u], it
follows that α(v) = β(v) for every vertex v ∈ V (G). By Proposition 4.1, β is an isometric
embedding of H into Qh. Thus, α is an isometric embedding of H into Qh. Moreover, by
Proposition 4.1, α is unique for a fixed embedding of vertices in N [v].
Corollary 4.3. Let G be a graph isomorphic to a daisy cube of order h. If v is a minimal
vertex of G and α an isometric embedding with α(v) = 0h, then α is proper.
Proof. Since v is a minimal vertex of G, there exist a proper embedding, say β, such that
β(v) = 0h. We may also assume w.l.o.g. that for every u ∈ N(v) we have β(u) = α(u).
From Lemma 4.2 then it follows that β(u) = α(u) for every v ∈ V (G).
Remark 4.4. If G is isomorphic to a daisy cube and α a proper embedding of G, then
different selections of labels for vertices of N(u) yield different but equivalent proper em-
beddings.
If G is a partial cube and α its isometric embedding to Qh, let Wi(G) denote the set of
vertices of G with weight i, i.e. Wi(G) = {v |w(α(v)) = i}.
We will also need the following result.
Proposition 4.5. If G is a partial cube, α its isometric embedding to Qh and v ∈ V (G)
such that w(α(v)) = i, then |N(v) ∩Wi−1(G)| ≤ i.
Proof. Since α is isometric embedding of G to Qh, for every v ∈ V (G) with w(α(v)) = i,
we have NG(v) ⊆ NQh(v). Moreover, |N(v) ∩ Wi−1(Qh)| = i and therefore |N(v) ∩
Wi−1(G)| ≤ i.
Proposition 4.6. Let G = Qh(X), x, y ∈ X̂ and x ̸= y. If u ∈ I(0h, x) and v ∈ I(0n, y)
such that u, v ̸∈ I(0n, x) ∩ I(0h, y) then uv ̸∈ E(G).
Proof. Suppose to the contrary that there exist u ∈ I(0h, x) and v ∈ I(0h, y) such that
u, v ̸∈ I(0h, x) ∩ I(0h, y) and d(u, v) = 1. Since X̂ is maximal, there exist at least two
indices i, j ∈ [h], such that xi ̸= yi and xj ̸= yj (otherwise we have either x ≤ y or
y ≤ x). Suppose w.l.o.g. xi = 1, yj = 1 and uk = vk for every k ∈ [h] \ {i, j}. If ui = 0
(resp. vj = 0), then u ∈ I(0h, y) (resp. v ∈ I(0h, x)). It follows that ui = vj = 1. But
then u = v and we obtain a contradiction.
A. Vesel: Efficient proper embedding of a daisy cube 277
Proposition 4.7. Let G = Qh(X), Xu be the maximal subset of X̂ such that u ∈
∩x∈XuI(0h, x) and Gu = G[∪x∈XuI(0h, x)]. If u ∈ V (G) and d(u) = h, then N(u) ⊆
V (Gu).
Proof. Suppose to the contrary that there exists v ∈ N(u) such that v ̸∈ ∪x∈XuI(0h, x).
It follows that there exists y ∈ X̂ − Xu such that v ∈ I(0h, y). Since u ∈ I(0h, x) for
some x ∈ X̂ and x ̸= y, Proposition 4.6 yields a contradiction.
Proposition 4.8. Let G = Qh(X), u ∈ V (G) and Xu be the maximal subset of X̂ such
that u ∈ ∩x∈XuI(0h, x). If d(u) = h, then | ∪x∈Xu Sx| = h.
Proof. Suppose | ∪x∈Xu Sx| < h. It follows that there exist j ∈ [h] such that for all
v ∈ ∪x∈XuI(0h, x) we have vj = 0. Since d(u) = h , there exists z ∈ N(u) such that
zj = 1. It follows that z ̸∈ ∪x∈XuI(0h, x). Thus, there exists y ∈ X̂ − Xu such that
v ∈ I(0h, y). Proposition 4.7 yields a contradiction.
Lemma 4.9. Let G = Qh(X) and u ∈ V (G) such that d(u) = h. Then |Nu(v)| ≥ 2 for
every v ∈ V (G) \N [u].
Proof. Let Xu be the maximal subset of X̂ with the property u ∈ ∩x∈XuI(0h, x) and
Gu = G[∪x∈XuI(0h, x)]. By Lemma 3.1 and Lemma 2.1, Gu is a daisy cube and u its
minimal vertex. It follows that the lemma holds for every v ∈ V (Gu). Suppose then that
v ̸∈ ∪x∈XuI(0h, x). Thus, there exists y ∈ X̂ − Xu, such that v ∈ I(0h, y). Note that
Su ⊆ ∩x∈XuSx.
Let Su+ = {i |ui = 1 and vi = 0} and Su− = {i | vi = 1 and ui = 0}.
We first show that |Su−| ≠ 1. Suppose to the contrary that there exists exactly one
index i ∈ [h] \ Su+, such that vi = 1 and ui = 0. Since d(u) = h, by Proposition 4.8,
there exists x ∈ Xu such that xi = 1. Note also that Su ⊆ Sx and since xi = 1, we have
Sv ⊆ Sx. It follows that v ≤ x and we obtain a contradiction.
If |Su+| = 0, then vertices of I(u, v) induce a |Su−|-cube in G. Thus, v admits |Su−|
neighbors at distance d(u, v)−1 from u. Clearly, |Su+| = 0 implies |Su−| > 0. Moreover,
since we show above that |Su−| ≠ 1, we have |Su−| ≥ 2 and the case is settled.
If |Su+| > 0, we may find i, j ∈ Su− such that i ̸= j. Let z and z′ be vertices
obtained from v by setting the i-th and j-th coordinate to zero, respectively. Obviously,
z, z′ ∈ Nu(v).
Since we show that we obtain |Nu(v)| ≥ 2 for every value of |Su+|, the lemma holds
for every v ∈ V (G) \N [u]. This assertion concludes the proof.
Lemma 4.9 is the basis for the next algorithm which finds an isometric embedding for
an unlabeled graph isomorphic to a daisy cube of dimension h.
Procedure Embedding(G, h, β, u);
1. u is a vertex of degree h in G;
2. β(u) := 0h;
3. i := 1;
4. Q := ∅; {Q is an empty queue}
5. for all v ∈ V (G) do p(v) := 0;
6. for all v ∈ N(u) do begin
β(v) := 0i−110h−i;
278 Ars Math. Contemp. 21 (2021) #P2.07 / 271–282
0000
1100
0001
1101
1101
0001
1001
0101
0100
1000
1011
0111
0101
1001
1000
0100
0111
1011
1111
0011
1100 0000
0010
1110
1110
0010
1010
0110
0110 1010
x
u
y
z
Figure 2: An isometric (left) and proper (right) embedding of a daisy cube isomorphic to
Q−4 .
i := i+ 1;
p(v) := u;
Insert v in the end of Q;
end;
7. while Q ̸= ∅ do begin
7.1 Remove the first vertex v from Q;
7.2. for all z ∈ N(v) do
if p(z) = 0 then begin
p(z) := v;
Append z to the end of Q;
end
else β(z) := β(v) ∨ β(p(z));
end.
Theorem 4.10. If G is a daisy cube, then an isometric embedding of G can be found in
linear time.
Proof. Note first that Lemma 4.2 defines the procedure to construct an isometric embed-
ding of G into Qh. Let α and β be isometric embeddings as defined in Lemma 4.2 and
algorithm Embedding, respectively. Suppose that u is the vertex being labeled 0h both by
the algorithm and by the construction of Lemma 4.2. Clearly, for every v in N [u] we could
have α(v) = β(v). Note also that in the essence the algorithm performs a BFS search
in G (see for example [4, Section 17.3]). Thus, for every z ∈ N(v) of Step 7.2 we have
d(u, z) = d(u, p(z)) + 1 = d(u, v) + 1. It follows that v, p(z) ∈ Nu(z). By Lemma 4.9,
since d(u) = h, for every v ∈ V (G)\N [u] we have |NuG(v)| ≥ 2. Therefore, α(z) = β(z)
for every z ∈ V (G) \N [u].
For the time complexity of the algorithm, note that the number of the executions of the
body of the loop in Step 7.2 is bounded by the number of edges of a graph. Since the time
complexity of the body of the loop is constant, the overall number of step of the algorithm
is linear in the number of the edges of the graph.
A. Vesel: Efficient proper embedding of a daisy cube 279
5 Proper embedding
Lemma 5.1. Let G be a daisy cube of Qh, v a minimal vertex of G and u a vertex of degree
h of G. If β is an isometric embedding of G such that β(u) = 0h, then vβ ◦ β is a proper
embedding of G.
Proof. Note that vβ(β(v)) = 0h. Since β is isometric, it is easy to see that vβ ◦ β is also
isometric. Corollary 4.3 now yields the assertion.
Let u be a vertex of degree h of G = Qh(X). Let Xu be the maximal subset of X̂
with the property u ∈ ∩x∈XuI(0h, x) and Gu = G[∪x∈XuI(0h, x)]. Recall that Gu is a
daisy cube of Qh and u its minimal vertex. If β is an isometric embedding of G such that
β(u) = 0h, let Y u be the set of maximal vertices of Gu with respect to u and let Zu be the
set of vertices z of V (G) \ V (Gu) with the property Nu(z) = N(z).
Proposition 5.2. Let u be a vertex of degree h of G = Qh(X). If β is an isometric
embedding of G such that β(u) = 0h, then Y u = {y |β(y) = x and x ∈ Xu}.
Proof. As noted above, Gu is a daisy cube of Qh and u its minimal vertex. Since u is
of degree h and β(u) = 0h, the restriction of β to V (Gu) is a proper embedding of Gu.
Moreover, since every permutation of indices of a proper embedding yields an equivalent
embedding, we may assume w.l.o.g. that for every z ∈ N(u) we have β(z) = 0i−110h−i
if and only if ui ̸= zi. It follows that for every w ∈ N(0h) we have uβ(β(w)) = w.
By Lemma 3.1, uβ ◦ β is proper. Moreover, by Lemma 4.2, uβ(β(v)) = v for every
v ∈ V (Gu). From Lemma 3.1 then follows that Y u = {y |β(y) = x and x ∈ Xu}.
Proposition 5.3. Let u be a vertex of degree h of G = Qh(X) and z ∈ Zu. If β is
an isometric embedding of G and β(u) = 0h, then there exists y ∈ X̂ − Xu such that
z ∈ I(0h, y). Moreover,
β(i)(z) =
{
0, i ∈ Su
yi, i ̸∈ Su
Proof. Let Xu be the maximal subset of X̂ with the property u ∈ ∩x∈XuI(0h, x). By
Lemma 2.1, since z ̸∈ ∪x∈XuI(0h, x), there must be y ∈ X̂ −Xu such that z ∈ I(0h, y).
By Nu(z) = N(z), we have d(u, z) ≥ d(u, v) for every v ∈ I(0h, y). If vi = 1 for
some i ∈ Su, then let v′ be the vertex of G such that v′j = vj for every j ̸= i and
v′i = 0. Obviously, v
′ ≤ y, thus v′ ∈ I(0h, y). Moreover, since β(i)(v′) = 1, we have
d(u, v′) > d(u, v) and we obtain a contradiction. It follows that the assertion holds for
every i ∈ Su. If i ̸∈ Su, then β(i)(v) = vi for every v ∈ I(0h, y). Since y is maximal in
I(0h, y), the assertion follows.
Theorem 5.4. Let u be a vertex of degree h of G = Qh(X). If β is an isometric embedding
of G such that β(u) = 0h, ŷ = ∧y∈Y uβ(y), ẑ = ∧z∈Zuβ(z)(∧1h) and v = β−1(ŷ ∧ ẑ),
then v is the minimal vertex of G with respect to vβ ◦ β.
Proof. Note first that β = β−1, thus, for every b ∈ Bh and every i ∈ [h] it holds
β(i)(b) = β
−1
(i) (b) =
{
b̄i, i ∈ Su
bi, i ̸∈ Su
(5.1)
280 Ars Math. Contemp. 21 (2021) #P2.07 / 271–282
Let x̂ = ∧x∈Xux. By Proposition 5.2, we have Y u = {y |β(y) = x and x ∈ Xu}.
Thus, x̂ = ŷ. Note that by Proposition 3.2, every minimal vertex of G belongs to I(0h, x̂).
If Xu = X̂ , then Zu = ∅ and we get β−1(ŷ ∧ ẑ) = β−1(ŷ) = β−1(x̂). By equation
(5.1), we have β−1(x̂) ≤ x. It follows that β−1(x̂) ∈ I(0h, x̂) and we are done.
Otherwise, let z ∈ Zu be such that z ∈ I(0h, y) for some y ∈ X̂ − Xu. We
have to show that β−1(x̂ ∧ β(z)) is a minimal vertex of ∪x∈XuI(0h, x) ∪ I(0h, y), i.e.
Sβ
−1(x̂∧β(z)) ⊆ Sx̂∧y .
By Proposition 5.3, we have
β(i)(z) =
{
0, i ∈ Su
yi, i ̸∈ Su
Since Su ⊆ Sx̂, we have
(x̂ ∧ β(z))i =
{
yi, i ̸∈ Sx̂ \ Su
0, otherwise
By equation (5.1), we have β−1i (x̂ ∧ β(z)) = 0 for every i ∈ [h] \ Sx̂∧y . Since we can
repeat the above discussion for every z ∈ Zu, we showed that β−1(x̂ ∧ ẑ) = β−1(ŷ ∧ ẑ)
is a minimal vertex of G. Moreover, since by Lemma 5.1 it follows that β
−1(ŷ∧ẑ)β ◦ β is a
proper embedding of G, the proof is complete.
Figure 2 shows two embeddings of a daisy cube G isomorphic to Q−4 . The embedding
β on the left hand side is determined such that β(u) = 0000 (note that d(u) = 4). Since u is
not minimal in G, the embedding β is isometric but not proper. From Xu = Y u = {x, y}
and Zu = {z} we get ŷ = 1110∧1101 = 1100, ẑ = 1111 and ŷ∧ẑ = 1100∧1111 = 1100.
Moreover, the minimal vertex of G is v = β−1(1100) and vβ ◦ β is the proper embedding
of G as described in Lemma 5.1. That is to say, we obtain the proper embedding of G by
assigning β(w)⊕ 1100 to every w ∈ V (G).
Theorem 5.4 is the basis for the next algorithm, which finds a proper embedding of a
graph isomorphic to a daisy cube of dimension h.
Procedure Proper(G, h, α);
1. Embedding(G, h, β, u);
2. for i := 1 to h+ 1 do Wi := ∅;
3. for all v ∈ V (G) do Ww(β(v)) := Ww(β(v)) ∪ {v};
4. for all v ∈ V (G) do q(v) := 0;
5. for i := 1 to h do begin
5.1. for all x ∈ Wi do
5.1.1 if
∑
y∈N(x)∩Wi−1 q(y) = i(i− 1) then begin
q(x) := i;
for all y ∈ N(x) ∩Wi−1 do q(y) := 0;
end
5.1.2 else if N(x) ∩Wi+1 = ∅ then q(x) := i
6. s := 1h;
7. for all v ∈ V (G) do
7.1. if q(v) ̸= 0 then s := s ∧ β(v);
8. for all v ∈ V (G) do α(v) := s⊕ β(v);
end.
A. Vesel: Efficient proper embedding of a daisy cube 281
Theorem 5.5. A proper embedding of an unlabeled graph isomorphic to a daisy cube can
be found in linear time.
Proof. We first show that the algorithm Proper finds a proper embedding of G. As shown
in Theorem 4.10, embedding β provided by the algorithm Embedding is isometric. With
respect to Theorem 5.4 and Step 7, we have to show that if q(v) ̸= 0, then either v ∈ Y u
or v ∈ Zu. Clearly, in Step 3, all vertices at distance i from u are inserted in Wi, while in
Step 4, q(v) is set to 0 for every v ∈ V (G). The value of q(v) is altered either in Step 5.1.1
or in Step 5.1.2.
Let w(x) = i. We show that q(x) = i in the i-th iteration of for loop if and only if
either I(u, x) induces an i-cube or x ∈ Zu. Note that I(u, x) induces an i-cube, if and only
|N(x)∩Wi−1| = i and for every y ∈ N(x)∩Wi−1 the set I(u, y) induces a (i− 1)-cube.
Moreover, if x ∈ Y u, then I(u, x) induces a maximal i-cube in Gu.
In the first iteration of Step 5, for every vertex of W1 the value of q is set to 1. In the
next iteration, when a vertex x of W2 is considered, these values for two vertices of W1,
say y and y′, are set to zero if {u, y, y′, x} induce a 2-cube. Thus, for every x, y ∈ W1∪W2
we have
- q(y) = 1 if and only if x ∈ N(u) and there is no vertex y ∈ W2 such that I(u, y) ⊆
I(u, x) and I(u, x) induces Q2.
- q(x) = 2 if and only I(u, x) induces Q2.
Suppose now that for i ≥ 3 and y ∈ Wi−1 it holds that q(y) = i−1 if and only if I(u, y)
induces a maximal cube in G[W1∪W2 . . .∪Wi−1] or Nu(y) = N(y); otherwise, q(y) = 0.
Let w(x) = i. Note that |N(x) ∩ Wi−1| ≤ i by Proposition 4.5. Thus, the condition of
the if statement in Step 5.1.1 is fulfilled if and only if for every y ∈ N(x)∩Wi−1 we have
q(y) = i − 1, i.e. for every y ∈ N(x) ∩Wi−1 the set I(u, y) induces an (i − 1)-cube. If
the condition of the if statement returns true, then q(x) obtains the value i while for every
y ∈ N(x) ∩Wi−1 the value of q(y) is set to 0. If the condition of the if statement returns
false, then q(x) is set to i if and only if N(x) ∩Wi+1 = ∅, i.e. x ∈ Zu. Thus, we showed
that in the i-th iteration of the for loop q(x) = i if and only if either I(u, x) induces an i-
cube or x ∈ Zu. Since the claim holds for every i, we showed that if q(v) ̸= 0, v ∈ V (G),
then either v ∈ Y u or v ∈ Zu. From Theorem 5.4 then it follows that the string s computed
in Step 7 is equal to ŷ ∧ ẑ, where ŷ = ∧y∈Y uβ(y) and ẑ = ∧z∈Zuβ(z). By Theorem 5.4,
β−1(s) = v is a minimal vertex of G while the embedding α obtained in Step 8 is equal to
vβ ◦ β. Moreover, α is proper by Lemma 5.1.
In order to consider the time complexity of the algorithm, note first that all steps of the
algorithm except Step 5 can be executed in O(m) time, where m is the number of edges
of G. For the time complexity of Step 5 it is convenient to store the weights of vertices in
a vector, which allows that the weight of a vertex and therefore its inclusion in a set Wi
can be determined in constant time. Thus, the time complexity of Steps 5.1.1 and 5.1.2
is linear in the number of edges incident with the vertex x. Since Step 5 is performed for
every vertex of the graph, the total number of steps is bounded by the number of edges of
G. This assertion concludes the proof.
ORCID iDs
Aleksander Vesel https://orcid.org/0000-0003-3705-0071
282 Ars Math. Contemp. 21 (2021) #P2.07 / 271–282
References
[1] M. Aı̈der, S. Gravier and K. Meslem, Isometric embeddings of subdivided connected graphs
into hypercubes, Discrete Math. 309 (2009), 6402–6407, doi:10.1016/j.disc.2008.10.030.
[2] J. Azarija, S. Klavžar, Y. Rho and S. Sim, On domination-type invariants of Fibonacci cubes
and hypercubes, Ars Math. Contemp. 14 (2018), 387–395, doi:10.26493/1855-3974.1172.bae.
[3] P. Codara and O. M. D’Antona, Generalized Fibonacci and Lucas cubes arising from powers
of paths and cycles, Discrete Math. 339 (2016), 270–282, doi:10.1016/j.disc.2015.08.012.
[4] R. Hammack, W. Imrich and S. Klavžar, Handbook of product graphs, Discrete Mathematics
and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2nd edition, 2011, with a
foreword by Peter Winkler.
[5] W.-J. Hsu, Fibonacci cubes-a new interconnection topology, IEEE Trans. Parallel Distr. Sys-
tems 4 (1993), 3–12, doi:10.1109/71.205649.
[6] W. J. Hsu and M. J. Chung, Generalized fibonacci cubes, in: 1993 International Conference on
Parallel Processing - ICPP’93, volume 1, 1993 pp. 299–302, doi:10.1109/icpp.1993.95.
[7] A. Ilić, S. Klavžar and Y. Rho, Generalized Fibonacci cubes, Discrete Math. 312 (2012), 2–11,
doi:10.1016/j.disc.2011.02.015.
[8] A. Ilić and M. Milošević, The parameters of Fibonacci and Lucas cubes, Ars Math. Contemp.
12 (2017), 25–29, doi:10.26493/1855-3974.915.f48.
[9] S. Klavžar and M. Mollard, Daisy cubes and distance cube polynomial, European J. Combin.
80 (2019), 214–223, doi:10.1016/j.ejc.2018.02.019.
[10] H. M. Mulder, The interval function of a graph, volume 132 of Mathematical Centre Tracts,
Mathematisch Centrum, Amsterdam, 1980.
[11] E. Saygı, On the domination number and the total domination number of Fibonacci cubes, Ars
Math. Contemp. 16 (2019), 245–255, doi:10.26493/1855-3974.1591.92e.
[12] A. Taranenko, Daisy cubes: a characterization and a generalization, European J. Combin. 85
(2020), 103058, 10, doi:10.1016/j.ejc.2019.103058.
[13] A. Vesel, Cube-complements of generalized Fibonacci cubes, Discrete Math. 342 (2019),
1139–1146, doi:10.1016/j.disc.2019.01.008.
[14] P. Žigert Pleteršek, Resonance graphs of kinky benzenoid systems are daisy cubes, MATCH
Commun. Math. Comput. Chem. 80 (2018), 207–214.
[15] J. Wei, Y. Yang and G. Wang, Circular embeddability of isometric words, Discrete Math. 343
(2020), 112024, 11, doi:10.1016/j.disc.2020.112024.
[16] P. M. Winkler, Isometric embedding in products of complete graphs, Discrete Appl. Math. 7
(1984), 221–225, doi:10.1016/0166-218x(84)90069-6.