1 Introduction

A suitable interconnection network is an important part for the design of a multicomputer or multiprocessor system. Such a network is usually modeled by a symmetric graph, where the nodes represent the processing elements and the edges represent the communication channels. Desirable properties of an interconnection network include symmetry, embedding capabilities, relatively small degree, small diameter, scalability, robustness, and efficient routing [42]. One of the most efficient interconnection networks is the hypercube due to its structural regularity, potential for parallel computation of various algorithms, and the high degree of fault tolerance [43].

The hypercube has many excellent features and thus becomes the first choice of topological structure of parallel processing and computing systems. The machines based on hypercubes such as the Cosmic Cube from Caltech, the iPSC/2 from Intel, and Connection Machines have been implemented commercially [11]. Hypercubes are very popular models for parallel computation because of their symmetry and relatively small number of interprocessor connections. Among the hypercube-based interconnection networks designed for extremely large-scale supercomputers that were studied in the last decade, we mention metacubes [29], hierarchical cubic networks [6, 31], and k-ary n-cubes [16, 51]. The hypercube embedding problem is the problem of mapping a communication graph into a hypercube multicomputer. Hypercubes are known to simulate other structures such as grids and binary trees [9, 33].

Graph embedding is an important technique that maps a guest graph into a host graph, usually an interconnection network [7]. The quality of an embedding can be measured by certain cost criteria. One of these criteria considered very often is the dilation. The dilation of an embedding is defined as the maximum distance between a pair of vertices of the host graph that are images of adjacent vertices of the guest graph. It is a measure for the communication time needed when simulating one network on another [27]. A closely related and important cost criterion is the wirelength of an embedding which is the sum of the dilations in the host graph of edges in the guest graph. The wirelength of a graph embedding arises from VLSI design, data structures and data representations, networks for parallel computer systems, biological models that deal with cloning and visual stimuli, parallel architecture, structural engineering, and so on [25, 38, 49].

Another important cost criterion is the edge congestion. The edge congestion of an embedding is the maximum number of edges of the guest graph that are embedded on any single edge of the host graph. An embedding with a large edge congestion faces many problems, such as long communication delay, circuit switching, and the existence of different types of uncontrolled noise. In data networking, network edge congestion occurs when a link or node is carrying so much data that its quality of service deteriorates. Typical effects include packet loss or the blocking of new connections. Therefore, a minimum edge congestion is the most desirable feature in network embedding [12, 35].

Graph embeddings have been well studied for a number of networks [2, 3, 9, 12,13,14,15,16,17, 19, 26, 33, 34, 36, 40, 41, 44, 49]. While in actual supercomputing applications it is usually not sufficient to be able to embed individual graphs optimally, a good understanding of the embedding behavior of single graphs can provide insights to support the development of methodologies and algorithms for solving the more complex problems arising in practice. In this paper, we study the dilation, wirelength, and congestion of embeddings of graphs into hypercubes and proceed as follows. In the next section, concepts needed are formally introduced. In Sect. 3, we consider the dilation of embedding into \(Q_n\) and in the main result characterize the graphs G with \({{\,\mathrm{dil}\,}}(G, Q_n)\le n-1\): they are precisely the graphs which contain a perfect anti-matching. Then, in Sect. 4, we prove a general lower bound on the edge congestion and a lower bound on the wirelength of embeddings into hypercubes. Both bounds are expressed in terms of the bisection width. In the remainder of the paper, these results are applied to particular graphs which have been studied in the supercomputing literature before [6, 18, 32]. The specific results obtained in Sects. 5 to 8 are summarized in Table 1, where \(K_{2^{n-p},\dots ,2^{n-p}}\), \(FQ_n\) and \(W_{2^n}\) denote the complete \(2^p\)-partite graph with parts of size \(2^{n-p}\), the folded n-hypercubes and the \(2^n\)-wheel, respectively, and \(G\square H\) is the cartesian product of two graphs G and H (following standard notation in the graph theory literature, see for instance [24]). All of these graphs are defined precisely in the sections containing the corresponding results.

Table 1 Summary of the results in Sects. 5 to 8
Full size table

2 Preliminaries

In this section, we give basic definitions and preliminaries related to embedding problems. Let G and H be finite graphs. Then an embedding of G into H is a pair \((f,P_f)\), where \(f: V(G)\rightarrow V(H)\) is a one-to-one mapping and \(P_f\) is a mapping from E(G) to the set of paths in H such that each edge \(e=uv\in E(G)\) is assigned a path \(P_f(e)\) in H between f(u) and f(v). By abuse of language, we will also refer to an embedding \((f, P_f)\) simply by f.

The length of \(P_{f}(e)\) is the dilation \({{\,\mathrm{dil}\,}}_f(e)\) of the edge e (with respect to the embedding \((f,P_f)\)). The maximum dilation over all edges of G is called the dilation of the embedding. The dilation of embedding G into H is the minimum dilation taken over all embeddings of G into H and denoted by \({{\,\mathrm{dil}\,}}(G,H)\), cf. [3]. In other words,

$$\begin{aligned} {{\,\mathrm{dil}\,}}(G,H)=\min _f\max _{e\in E(G)} {{\,\mathrm{dil}\,}}_f(e), \end{aligned}$$

where the minimum is taken over all injections \(f:V(G)\rightarrow V(H)\). It is not necessary to specify \(P_f\) when we are interested in the dilation of embedding G into H, because we can take \(P_f(uv)\) to be any shortest path between f(u) and f(v). The diameter of H, denoted by \({{\,\mathrm{diam}\,}}(H)\), is the maximum distance between any two vertices of H, and this provides a trivial upper bound for \({{\,\mathrm{dil}\,}}(G,H)\).

The wirelength of an embedding \(f= (f, P_f)\) of G into H is

$$\begin{aligned} WL_{f}(G,H) = \sum _{e_G\in E(G)}{{\,\mathrm{dil}\,}}_f(e_G), \end{aligned}$$
(1)

and the wirelength of embedding G into H is

$$\begin{aligned} WL(G,H)=\underset{f}{\min }\,WL_{f}(G,H), \end{aligned}$$

see [33]. We also refer to [2, 3, 37] for the search of embeddings of G into H that attain the value WL(G, H).

Let \(f = (f, P_f)\) be an embedding of G into H. For \(e=uv\in E(H)\), let \(EC_{f}(e)\) denote the number of edges \(e'\in E(G)\) such that e is in the path \(P_{f}(e')\) between f(u) and f(v) in H. Then the edge congestion of f is

$$\begin{aligned} EC_{f}(G,H)=\max _{e\in E(H)} EC_{f}(e) \end{aligned}$$

and the edge congestion of embedding G into H is

$$\begin{aligned} EC(G,H)=\min _fEC_{f}(G,H), \end{aligned}$$

where the minimum is taken over all embeddings \(f = (f, P_f)\) of G into H. Note that

$$\begin{aligned} WL_{f}(G,H) = \sum _{e_H\in E(H)}EC_{f}(e_H). \end{aligned}$$
(2)

The above problems can be specialized to several distance problems. For example, if the host graph is a path, then the dilation of embedding graph into a path is the bandwidth problem. Further distance problems are listed in Table 2, where \(P_n\), \(C_n\) and \(K_n\), are the path, the cycle, and the complete graph of order n, respectively, and \(K_{a,b}\) is the complete bipartite graphs on \(a+b\) vertices.

Table 2 Various embedding problems
Full size table

Let \(n\geqslant 1\). The n-cube (n-dimensional hypercube) has vertex set \(\{0,1\}^n\), and vertices \(x,y\in V(Q_{n})\) are adjacent if and only if the corresponding binary strings differ exactly in one bit. Equivalently, the vertices of \(Q_{n}\) can be identified with integers \(0,1,\dots ,2^n-1\), where vertices i and j are adjacent if and only if \(i-j=\pm 2^{p}\) for some integer \(p\geqslant 0\).

For disjoint subsets \(A,B\subseteq V(G)\) we will use the notation \(E_G(A,B)=\{uv\in E(G)\,|\, u\in A,\, v\in B\}\) and \(E_G(A)=\{uv\,|\, u,v\in A\}\). If x is a vertex of a graph G, then \(N_i(x)\) is the set of vertices in G at distance i from x. The maximum degree of G is denoted by \(\Delta (G)\) and its order by n(G).

3 Graphs with large dilation of embedding into hypercubes

The dilation, the wirelength, and the edge congestion problem are different in the sense that an embedding that gives the minimum dilation need not give the minimum congestion (wirelength) and vice-versa. From \({{\,\mathrm{diam}\,}}(Q_n)=n\), we obtain immediately the upper bound \({{\,\mathrm{dil}\,}}(G,Q_n)\leqslant n\) for every graph G. To characterize graphs G of order \(2^n\) with \({{\,\mathrm{dil}\,}}(G, Q_n)=n\), we need the following concept. A pair \((u,u')\in V(G){\times V(G)}\), is said to be an antipodal pair (of vertices) if the distance between u and \(u'\) is equal to the diameter of G. If this is the case, we also say that \(u'\) is an antipodal vertex of u and u is an antipodal vertex of \(u'\). In the hypercube \(Q_n\), every vertex \(u\in V(Q_n)\) has a unique antipodal vertex which we denote by \(\bar{u}\). If G is a graph, then the set of pairs of vertices \(X = \{\{x_1,y_1\}, \dots , \{x_k,y_k\}\}\) forms an anti-matching, if \(x_1y_1\notin E(G),\ldots , x_ky_k\notin E(G)\). That is, X is an anti-matching if \(x_1y_1, \ldots , x_ky_k\) form a matching in the complement of G, that is, the graph which has the same vertex set as G, and edge set \(\{xy\,\vert \,x,y\in V(G),\,xy\not \in E(G)\}\). In addition, we say that X is a perfect anti-matching if \(2|X| = n(G)\). Now we have the following characterization.

Theorem 1

Let G be a graph of order \(2^n\). Then \({{\,\mathrm{dil}\,}}(G,Q_n)\leqslant n-1\) if and only if G contains a perfect anti-matching.

Proof

Let \({{\,\mathrm{dil}\,}}(G,Q_n)\leqslant n-1\) and let \((f, P_f)\) be a corresponding embedding of G into \(Q_n\), that is, \({{\,\mathrm{dil}\,}}_f(G,Q_n)={{\,\mathrm{dil}\,}}(G,Q_n)\). Consider the partition \(X' = \{ \{u,\overline{u}\}\,|\,u\in V(Q_n)\}\) of \(V(Q_n)\) into \(2^{n-1}\) antipodal pairs. If \(e=\{f^{-1}(u),f^{-1}(\bar{u})\}\in E(G)\) for some \(u\in V(Q_n)\), then

$$\begin{aligned} {{\,\mathrm{dil}\,}}_f(G,Q_n)\geqslant {{\,\mathrm{dil}\,}}_f(e)\geqslant {{\,\mathrm{dist}\,}}_{Q_n}(u,\bar{u})=n, \end{aligned}$$

and this contradicts the assumption. We conclude that \(f^{-1}(u)\) is not adjacent to \(f^{-1}(\overline{u})\), and it follows that \(X = \{ \{f^{-1}(u),f^{-1}(\overline{u})\}\,|\,u\in V(Q_n)\}\) is a perfect anti-matching.

Conversely, let X be a perfect anti-matching of G. We now define an embedding \((f, P_f)\) of G into \(Q_n\) by mapping each pair \(\{x,y\}\) from X into an antipodal pair of vertices of \(Q_n\), that is, \(\{f(x), f(y)\} = \{v, \overline{v}\}\) for some \(v\in V(Q_n)\). Since each vertex of \(Q_n\) has a unique antipodal vertex, it follows that \({{\,\mathrm{dil}\,}}_f(e) \le n-1\) for each edge e of G and hence \({{\,\mathrm{dil}\,}}(G, Q_n)\leqslant n-1\). \(\square \)

To determine a large class of graphs G with \({{\,\mathrm{dil}\,}}(G,Q_n)=n-1\) we state the following lemma that could be applied elsewhere.

Lemma 1

If G is a graph of order \(2^n\), then

$$\begin{aligned} {{\,\mathrm{dil}\,}}(G,Q_n)\geqslant \max \left\{ k\,:\,\sum _{i=1}^{k-1}\left( {\begin{array}{c}n\\ i\end{array}}\right) <\Delta (G)\right\} . \end{aligned}$$

Proof

Let k be a positive integer satisfying \(\left( {\begin{array}{c}n\\ 0\end{array}}\right) +\dots +\left( {\begin{array}{c}n\\ k-1\end{array}}\right) <\Delta (G)\), and let \((f, P_f)\) be an embedding of G into \(Q_n\). Let u be a vertex of G with \(\deg (u) = \Delta (G)\) and let \(f(u) = v\in V(Q_n)\). Setting \(X = N_1(v)\cup \dots \cup N_{k-1}(v)\), the assumption on k implies that

$$\begin{aligned} |X| = |N_1(v)|+\cdots +|N_{k-1}(v)| = \sum _{i=1}^{k-1} \left( {\begin{array}{c}n\\ i\end{array}}\right) < \Delta (G). \end{aligned}$$

Thus, there exists at least one vertex w of G adjacent to u such that \(f(w)\in V(Q_n)\setminus X\). It follows that the length of \(P_f(uw)\) is at least k and consequently \({{\,\mathrm{dil}\,}}(G, Q_n)\geqslant k\). \(\square \)

Combining Lemma 1 with Theorem 1 we obtain the following corollary.

Corollary 1

If G is a graph of order \(2^n\) with \(\Delta (G)\ge 2^n-n-1\) that contains a perfect anti-matching, then \({{\,\mathrm{dil}\,}}(G,Q_n) = n-1\).

Proof

By Theorem 1, \({{\,\mathrm{dil}\,}}(G,Q_n) \le n-1\) and the reverse inequality follows from Lemma 1 and

$$\begin{aligned} \sum _{i=1}^{n-2}\left( {\begin{array}{c}n\\ i\end{array}}\right) =2^n-\left( {\begin{array}{c}n\\ 0\end{array}}\right) -\left( {\begin{array}{c}n\\ n-1\end{array}}\right) -\left( {\begin{array}{c}n\\ n\end{array}}\right) =2^n-n-2<\Delta (G). \quad \square\end{aligned}$$

For illustration, consider \(G=K_{4,4,4,4}\). Then \(\Delta (G) = 12 \ge 2^4-4-1\). Since G contains a perfect anti-matching, \({{\,\mathrm{dil}\,}}(G, Q_4) = 3\). In Fig. 1 a corresponding embedding is shown.

Fig. 1
figure 1

An embedding of \(K_{4,4,4,4}\) into \(Q_4\) with dilation 3. The vertices of \(K_{4,4,4,4}\) are labeled such that we can take f to be the identity. The perfect anti-matching in G consists of the pairs \(\{i,15-i\}\) for \(i=0,1,\dots ,7\)

Full size image

4 Two lower bounds in terms of the bisection width

In this section, we give a general lower bound on the edge congestion and on the wirelength of embedding into hypercubes. Both bound involve the bisection width that is defined as follows. The bisection width BW(G) of a graph G is the minimum number of edges necessary in an edge cut so that the sizes of the two sides of the cut differ by at most one.

The first lower bound is established by the following averaging argument.

Theorem 2

If G and H are graphs of the same order, then

$$\begin{aligned} EC(G, H)\geqslant \frac{BW(G)}{BW(H)}. \end{aligned}$$

Proof

Set \(n = n(G)\) \((= n(H))\). Let \(A\cup B\) be a partition of V(H) such that \(|A|=\lceil n/2\rceil \), \(|B|=\lfloor n/2\rfloor \), and \(|E_H(A,B)|=BW(H)\), and let \(f:G\rightarrow H\) be an embedding with \(EC_f(G,H)=EC(G,H)\). Then

$$\begin{aligned} BW(G)\leqslant \left|E_G(f^{-1}(A), f^{-1}(B))\right|\leqslant \sum _{e\in E_H(A,B)} EC_f(e). \end{aligned}$$
(3)

where the first inequality follows from the definition of the bisection width, and the second one from the fact that for every edge \(uv\in E_G(f^{-1}(A), f^{-1}(B))\) the path \(P_f(uv)\) has to use at least one edge from \(E_H(A,B)\). Finally, we conclude

$$\begin{aligned} \frac{BW(G)}{BW(H)}= & {} \frac{BW(G)}{\left|E_H(A,B)\right|}\leqslant \frac{1}{\left|E_H(A,B)\right|}\sum _{e\in E_H(A,B)} EC_f(e) \leqslant \max _{e\in E_H(A,B)} EC_f(e)\\\leqslant & {} \max _{e\in E(H)} EC_f(e)=EC_f(G,H)=EC(G,H). \end{aligned}$$

\(\square \)

Corollary 2

If G is a graph of order \(2^n\), then

$$\begin{aligned} EC(G, Q_n)\geqslant \frac{BW(G)}{2^{n-1}}. \end{aligned}$$

Proof

The result follows from Theorem 2 and the fact that \(BW(Q_n)=2^{n-1}\), see [46]. \(\square \)

The lower bound for the wirelength is the following.

Theorem 3

If G is a graph of order \(2^n\), then \(WL(G, Q_n)\geqslant n\cdot BW(G).\)

Proof

Let \(E(Q_n)=S_1\cup \dots \cup S_n\) be the partition of \(E(Q_n)\) where \(S_i\) consists of the edges whose incident vertices differ in the ith coordinate. Then \(Q_n\setminus S_i\) consists of two vertex-disjoint \((n-1)\)-cubes. Moreover, \( |S_i|=2^{n-1} = BW(Q_n)\), and we can now estimate as follows, where the minimum is taken over all embeddings of G into \(Q_n\):

$$\begin{aligned} WL(G,Q_n)= & \, \min \limits _f \sum _{e\in E(Q_n)} EC_{f}(e) = \min \limits _f \sum _{i=1}^{n} \sum _{e\in S_i} EC_{f}(e) {\mathop {\geqslant }\limits ^{3}} \min \limits _f \sum _{i=1}^{n} BW(G) \\= & \, n\cdot BW(G). \end{aligned}$$

The first equality above holds by (1) and (2), and the second equality follows because the sets \(S_i\) form a partition of \(E(Q_n)\). \(\square \)

5 Embeddings of complete multipartite graphs

In this section, we consider the complete p-partite graph \(G = K_{n_1,\dots , n_p}\) of order \(2^n\). Recall that G contains p independent sets containing \(n_i\), \(i\in [p]\), vertices, and all possible edges between vertices from different parts.

From Theorem 1 it follows that \({{\,\mathrm{dil}\,}}(G,Q_n) = n\) if at least one of the \(p_i\) is odd and \({{\,\mathrm{dil}\,}}(G,Q_n)\leqslant n-1\) otherwise (that is, if all the \(p_i\) are even). We will next determine the wirelengths of embedding certain complete p-partite graphs into n-cubes, and start by determining the bisection widths of balanced complete multipartite graphs.

Lemma 2

If G is the complete t-partite graph \(K_{2r,\dots ,2r}\), with 2tr vertices, \(t\geqslant 2\), \(r\geqslant 1\), then

$$\begin{aligned} BW(G)=r^2t(t-1). \end{aligned}$$

Proof

Let \(V(G)=A\cup B\) be a partition with \(|A|=|B|=tr\) such that A and B each contains half of the vertices in every maximal independent set. Then

$$\begin{aligned} BW(G)\leqslant & \, \left|E_G(A,B)\right|=|E(G)|-|E_G(A)|-|E_G(B)|\\= & \, 4r^2\left( {\begin{array}{c}t\\ 2\end{array}}\right) -2r^2\left( {\begin{array}{c}t\\ 2\end{array}}\right) =r^2t(t-1). \end{aligned}$$

For the reverse inequality, let \(V(G)=A\cup B\) be a partition with \(|A|=|B|=tr\) and \(|E_G(A,B)|=BW(G)\). For \(i=1,\dots ,t\), let \(n_i\) be the number of vertices of A in the i-th independent set. Then we apply the Cauchy-Schwarz inequality to obtain the bound

$$\begin{aligned} |E_G(A)|= & \, \sum _{1\leqslant i<j\leqslant t}n_in_j=\frac{1}{2}\left( \left( \sum _{i=1}^tn_i\right) ^2-\sum _{i=1}^tn_i^2\right) \\= & \, \frac{1}{2}\left( (tr)^2-\sum _{i=1}^tn_i^2\right) \leqslant \frac{r^2t(t-1)}{2}. \end{aligned}$$

For the same reason, \(|E_G(B)|\leqslant r^2t(t-1)/2\), and consequently,

$$\begin{aligned} BW(G)= & \, \left|E_G(A,B)\right|\\= & \, |E(G)|-\left( |E_G(A)|+|E_G(B)|\right) \geqslant 4r^2\left( {\begin{array}{c}t\\ 2\end{array}}\right) -r^2t(t-1)\\= & \, r^2t(t-1). \end{aligned}$$

\(\square \)

We now want to determine the wirelength for embedding the complete \(2^p\)-partite graph \(G=K_{2^{n-p},\ldots , 2^{n-p}}\), \(1\leqslant p<n\) into \(Q_n\). In the proof of the following theorem, it will be convenient to have an explicit notation for the function which maps a nonnegative integer to the bitstring corresponding to its binary representation. More specifically, we will use the function \(\phi :\mathbb {N}\rightarrow \{0,1\}^{\mathbb {N}}\), defined by

$$\begin{aligned} \phi \left( 2^{k-1}x_1+2^{k-2}x_2+2^{k-3}x_3+\dots +2^1x_{k-1}+2^0x_k\right) =x_1x_2\dots x_k. \end{aligned}$$

Theorem 4

If G is the complete \(2^p\)-partite graph \(K_{2^{n-p},\ldots , 2^{n-p}}\), where \(1 \leqslant p < n\), then

$$\begin{aligned} WL(G,Q_n) = n\cdot 2^{2n-p-2}\,(2^{p}-1). \end{aligned}$$

Proof

Combining Lemma 2 for \(t=2^p\) and \(r=2^{n-p-1}\) with Theorem 3, we obtain

$$\begin{aligned} WL(G,Q_n) \geqslant n\cdot BW(G)=n\cdot 2^{2n-p-2}\,(2^{p}-1). \end{aligned}$$

In order to prove the reverse inequality we construct an embedding \(f:G\rightarrow Q_n\) in the following way. Let \(V(G)=V_1\cup \dots \cup V_{2^p}\) be the partition of V(G) into \(2^p\) independent sets of size \(2^{n-p}\). Label the vertices of V(G) with the numbers \(0,1,2,\dots ,2^n-1\), in such a way that

$$\begin{aligned} V_i=\left\{ j2^{p+1}+i-1\,:\,j=0,1,2,\dots ,2^{n-p-1}-1\right\} \cup \left\{ j2^{p+1}-i\,:\,j=1,2,3,\dots ,2^{n-p-1}\right\} . \end{aligned}$$
(4)

Recall that \(V(Q_n) = \{0,1\}^n\) and define \(f:V(G)\rightarrow V(Q_n)\) by mapping \(x\in V(G)\) to its binary representation. In other words, f is the restriction of \(\phi \) to the set \(\{0,1,\dots ,2^n-1\}\), that is, \(x=2^{n-1}x_1+2^{n-2}x_2+\dots +2^0x_n\) is mapped to \(f(x) = \phi (x)= x_1 x_2 \dots x_n\). We will now show that for this embedding, \(WL_f(G,Q_n)=n\cdot 2^{2n-p-2}\,(2^{p}-1)\), which concludes the proof. For \(x,y\in \{0,1\}^n\), let d(x, y) denote their Hamming distance, that is, \(d(x,y)=|x_1-y_1|+\dots +|x_n-y_n|\), which is equal to the distance between x and y in \(Q_n\). It follows from (4) that, for every \(i\in \{1,\dots ,2^p\}\),

$$\begin{aligned} f(V_i)=\{0,1\}^{n-p-1}\times \{\phi (i-1),\,\phi (2^{p+1}-i)\}. \end{aligned}$$

For instance, for \(p=3\) and \(n=p+3=6\),

$$\begin{aligned} f(V_1)&= \left\{ \begin{matrix} 000000,\\ 010000,\\ 100000,\\ 110000,\\ 001111,\\ 011111,\\ 101111,\\ 111111 \end{matrix} \right\} ,&f(V_2)&= \left\{ \begin{matrix} 000001,\\ 010001,\\ 100001,\\ 110001,\\ 001110,\\ 011110,\\ 101110,\\ 111110 \end{matrix} \right\} ,&f(V_3)&= \left\{ \begin{matrix} 000001,\\ 010010,\\ 100010,\\ 110010,\\ 001101,\\ 011101,\\ 101101,\\ 111101 \end{matrix} \right\} ,&\text {etc.} \end{aligned}$$

If x is an arbitrary vertex in \(V_i\), and \(k\in \{1,\dots ,n\}\) is any of the positions, then exactly half of the elements of \(f(V_i)\) differ from f(x) in position k. For \(k\in \{1,2,\dots ,n-p-1\}\) this is because the first \(n-p-1\) positions run twice through the vertices of \(Q_{n-p-1}\), and for \(k\in \{n-p,\dots ,n\}\) it follows from the fact that \(\phi (i-1)\) and \(\phi (2^{p+1}-i)\) are antipodal vertices in \(Q_{p+1}\). As a consequence, for any fixed \(x\in V_i\),

$$\begin{aligned} \sum _{y\in V_i\setminus x}d(f(x),f(y))=\sum _{k=1}^{n}\frac{1}{2}\left|V_i\right|=n2^{n-p-1}, \end{aligned}$$

hence

$$\begin{aligned} \sum _{\{x,y\}\in \left( {\begin{array}{c}V_i\\ 2\end{array}}\right) }d(f(x),f(y))= & \, \frac{1}{2}\sum _{x\in V_i}\sum _{y\in V_i\setminus x}d(f(x),f(y))\\= & \, \frac{1}{2}\sum _{x\in V_i}n2^{n-p-1}=n2^{2(n-1-p)}. \end{aligned}$$

As this is true for every \(i\in \{1,2,\dots ,2^p\}\),

$$\begin{aligned} WL_f(G,Q_n)= & \, \sum _{\{x,y\}\in \left( {\begin{array}{c}V(Q_n)\\ 2\end{array}}\right) }d(x,y)-\sum _{i=1}^{2^p}\sum _{\{x,y\}\in \left( {\begin{array}{c}V_i\\ 2\end{array}}\right) }d(f(x),f(y))\\= & \, n2^{2n-2}-2^pn2^{2(n-1-p)}=n2^{2n-2-p}(2^p-1).\end{aligned}$$

\(\square \)

6 Embeddings of folded hypercubes

The n-dimensional folded hypercube \(FQ_{n}\) is the graph obtained from \(Q_{n}\) by adding, for every vertex \(x=x_{1}\ldots x_{n}\), the edge between x and its antipodal vertex \(\overline{x}=\overline{x}_{1}\ldots \overline{x}_{n}\), where \(\overline{x}_i=1-x_i\), cf. [49]. Folded hypercubes are of wide current interest in reliability and fault tolerance of interconnection networks, see [10, 25, 30, 50]. In this section, we add to the known results on folded hypercubes their wirelength.

Theorem 5

For all \(n\ge 2\), \(WL(FQ_n,Q_n)= n2^n\).

Proof

In [39] it was proved that \(BW(FQ_n)=2^{n}\), and with Theorem 3 this implies \(WL(FQ_n,Q_n)\geqslant n2^n\). To prove the reverse inequality, let \(\mathrm{id}:FQ_n\rightarrow Q_n\) be the identity embedding, that is, \(\mathrm{id}(v) = v\), for every \(v\in V(FQ_n)\) (and where the second v is considered as a vertex of \(Q_n\)). For this embedding, the \(n2^{n-1}\) edges of \(FQ_n\) that are also the edges of \(Q_n\) contribute \(n2^{n-1}\) to the wirelength. and each of the \(2^{n-1}\) antipodal edges contributes n to the wirelength. We conclude

$$\begin{aligned} WL_{\mathrm{id}}(FQ_n,Q_n) = n2^{n-1} + 2^{n-1} n = n\cdot 2^n. \end{aligned}$$

\(\square \)

7 Embeddings of wheels

Let \(n\ge 4\). The wheel \(W_n\) of order n is the graph obtained from a cycle \(C_{n-1}\) by adding a new vertex x and joining x to all the vertices of the cycle. Vertex x is called the hub of the wheel and the edges incident with x are spokes of the wheel. Since the hub vertex is adjacent to all other vertices, the wheel does not contain an anti-matching, and by Theorem 1, \({{\,\mathrm{dil}\,}}(W_{2^n}, Q_n) = n\). We next determine the wirelength of embedding \(W_{2^n}\) into \(Q_n\).

Theorem 6

If \(n\ge 2\), then \(WL(W_{2^n},Q_n)= (n+2)2^{n-1}\).

Proof

For every embedding the spokes contribute

$$\begin{aligned} \sum _{k=1}^nk\left( {\begin{array}{c}n\\ k\end{array}}\right) =n2^{n-1} \end{aligned}$$

to the wirelength. Since \(Q_n\) is bipartite, the \(2^n-1\) cycle edges contribute at least \(2^n\). This gives a lower bound of \(n2^{n-1}+2^n=(n+2)2^{n-1}\), and using a Gray code this bound can be achieved. \(\square \)

8 Embeddings of some Cartesian products

Recall that the Cartesian product \(G\,\square \,H\) of graphs G and H is the graph with the vertex set \(V(G) \times V(H)\), vertices (g, h) and \((g',h')\) being adjacent if either \(g=g'\) and \(hh'\in E(H)\), or \(h=h'\) and \(gg'\in E(G)\). For more information on this product see the book [24]. We will use the following result on the edge-isoperimetric problem for Cartesian products of complete graphs (see [5] for a survey of related results).

Theorem 7

([23]) Let \(G=K_{p_1}\,\square \,K_{p_2}\,\square \,\cdots \,\square \,K_{p_t}\) with \(p_1\leqslant p_2\leqslant \dots \leqslant p_t\), and let m be an integer with \(1\leqslant m\leqslant p_1p_2\cdots p_t\). If H is a subgraph of G with \(|V(H)|=m\), then \(|E(H)|\leqslant |E(H^*)|\), where \(H^*\) is the subgraph induced by the first m vertices in lexicographic order, where we take

$$\begin{aligned} V(G)=\left\{ (a_1,a_2,\dots ,a_t)\,:\,1\leqslant a_i\leqslant p_i\text { for }i=1,2\dots ,t\right\} , \end{aligned}$$

and the lexicographic order is defined by \((a_1,a_2,\dots ,a_t)<(b_1,b_2,\dots ,b_t)\) if there exists an index i with \(a_i<b_i\) and \(a_j=b_j\) for all \(j<i\).

As a corollary, we obtain the bisection widths for products of complete graphs.

Corollary 3

If \(G = K_{2p_1}\,\square \,K_{p_2}\,\square \,K_{p_3}\,\square \,\cdots \,\square \,K_{p_t} \quad \square\) with \(2p_1\leqslant p_2\leqslant p_3\leqslant \dots \leqslant p_t\), then \(BW(G)=p_1^2p_2\cdots p_t\).

Proof

We have \(|E(G)|=p_1p_2\cdots p_t\left( 2p_1+p_2+p_3+\dots +p_t-t\right) \), and for any \(A\subseteq V(G)\) with \(|A|=p_1p_2\cdots p_t\), Theorem 7 implies

$$\begin{aligned} |E_G(A)|\leqslant \frac{1}{2}p_1p_2\cdots p_t\left( p_1+p_2+\dots +p_t-t\right) \end{aligned}$$

with equality if A is the set of vertices \((a_1,\dots ,a_t)\) with \(a_1\leqslant p_1\) or the set of vertices \((a_1,\dots ,a_t)\) with \(a_1>p_1\). This implies that for every partition \(V(G)=A\cup B\) with \(|A|=|B|=p_1p_2\cdots p_t\),

$$\begin{aligned} |E_G(A,B)|= & \, |E(G)|-|E_G(A)|-|E_G(B)|\\\geqslant & \, p_1p_2\cdots p_t\left( 2p_1+p_2+p_3+\dots +p_t-t\right) -p_1p_2\cdots p_t\left( p_1+p_2+\dots +p_t-t\right) \\= & \, p_1^2p_2\cdots p_t \end{aligned}$$

with equality if A is the set of vertices \((a_1,\dots ,a_t)\) with \(a_1\leqslant p_1\). \(\square \)

Theorem 8

Let n be a positive even integer, and let \(G=K_{2^{n/2}}\,\square \,K_{2^{n/2}}\). Then

$$\begin{aligned} WL(G,Q_{n})= n2^{3n/2-2}. \end{aligned}$$

Proof

From Corollary 3 with \(t=2\), \(p_1=2^{n/2-1}\) and \(p_2=2^{n/2}\), we obtain \(BW(G)=2^{3n/2-2}\), and together with Theorem 3 this implies the lower bound. To prove the upper bound we embed G into \(Q_n\), by mapping a vertex \((a,b)\in V(G)=\{0,1,\dots ,2^{n/2}-1\}\times \{0,1,\dots ,2^{n/2}-1\}\) with

$$\begin{aligned} a&= \sum _{i=1}^{n/2}a_i2^{n/2-i},&b&= \sum _{i=1}^{n/2}b_i2^{n/2-i} \end{aligned}$$

to the binary string \(a_1a_2\ldots a_{n/2}b_1b_2\ldots b_{n/2}\in \{0,1\}^n=V(Q_n)\). For \(i\in \{1,\dots ,n\}\), let \(V(Q_n)=A_i\cup B_i\) be the partition with \(A_i=\{x\in V(Q_n)\,:\,x_i=0\}\) and \(B_i=\{x\in V(Q_n)\,:\,x_i=1\}\). Then

$$\begin{aligned} E(Q_n)=\bigcup _{i=1}^nE_{Q_n}(A_i,B_i) \end{aligned}$$

and since each of the sets \(f^{-1}(A_i)\) and \(f^{-1}(B_i)\) induces a subgraph of G isomorphic to \(K_{2^{n/2-1}}\,\square \,K_{2^{n/2}}\), we obtain

$$\begin{aligned} WL_f(G,Q_n)= & \, \sum _{i=1}^n\sum _{e\in E_{Q_n}(A_i,B_i)}EC_f(e)=\sum _{i=1}^n\left|E_G\left( f^{-1}(A_i),f^{-1}(B_i)\right) \right|\\= & \, \sum _{i=1}^nBW(G) = n\cdot BW(G)= n2^{3n/2-2}. \end{aligned}$$

\(\square \)

9 Concluding remarks

In this paper, we have obtained lower bounds for dilation, wirelength, and edge congestion of an embedding of graphs into n-cubes. In particular, we found lower bounds for congestion and wirelength in terms the bisection width of the guest graph. This technique allows the computation of the exact dilation and wirelength for a range of networks. An open problem remains to determine the edge congestion of these networks. It also opens up the study of embedding parameters which remains unsolved for several good candidates of guest architectures. Another direction for extending our work to make it more directly applicable is the study of weighted versions of the embedding problem.