For n > 0, the hypercube of dimension n, denoted by Qn, is an undirected graph.The vertex set V(Qn)={0,1}nof Qnconsists of all n-tuples over a two letter alphabet {0,1}.For any u,v ∈V(Qn), {u,v} ∈E(Qn), the edge set of Qn, if and only if u,v differ in exactly one coordinate.

The circuit of length n, denoted by Cn, is an undirected graph with

We want to study the minimal wirelength of Qninto C2n, which is also called the circular wirelength for hypercubes.We show

Theorem 1.1For any n ≥1,

where ξnis the embedding corresponding to the Gray coding of order n.

For any S ?V(Qn), we denote that

For each 0 ≤k ≤2n, we set

where |A| is the number of elements in a finite set A.The characterization of sets S ?V(Qn)with |S|=k such that θ(n,S)=θ(n,k) is called the discrete isoperimetric problem for hypercubes.It was proven in [2, 8, 9] that θ(n,S)=θ(n,k) if and only if S is a cubal, which will be defined later.

It is interesting to review Harper’s solution[2, 8]on WL(Qn,P2n); the minimal wirelength of hypercube to path.Here Pkfor k >0 is an undirected graph called a path with

Instead of minimizing each item in the summation,Guu[6]wanted to prove that the summation as a whole is minimized by gray coding.

Given any S ?V(Qn), Guu [6] introduced a useful index:

Here Hnis the set of 2n half planes of Qn.A half plane H is composed of all x1···xn∈{0,1}nwith xi= a for some 1 ≤i ≤n and a ∈{0,1}.It is clear that 0 ≤Type(S)≤|S|/2.Without causing confusion, for any n>0, 0 ≤k ≤2n, 0 ≤t ≤k/2, we write

Figure 1 shows the sequences in the case of n = 6 for a gray coding and an embedding η(presented at the end of the note).Guu[6]showed that there are at least two i with 1 ≤i ≤2n?1such that tη,i≥2n?3.

Figure 1 Case n=6

It can be proved that, for 1 ≤i ≤2n?1, 0 ≤tξn,i≤2n?3and

Guu defined a sequence of function an(x,y) (see (4.7)) for any real 0 ≤y

and, for any d ≥1, that

It is also satisfied that, for any n>m>1, 0

Moreover, letting U =[i/2n,(i+1)/2n]×[j/2n,(j+1)/2n] with 0 ≤i <2n?1, 0 ≤j

Since 170/212< 1/24< 171/212, and a12(0.5,170/212) < f(0.5), Guu’s method is not enough to cover Theorem 1.2.We will divide the rectangle [0,1/2]×(1/24,171/212) into three subsets to complete the proof of Theorem 1.2.

Theorem 1.3([6, Theorem 16]) For any integers n,k,t with n ≥5 and

It is clear that Theorems 1.2 and 1.3 imply (1.3).

Some scholars [1, 5] pointed out that, in the proving of Theorem 1.3, Guu [6] took S =S1∪S2with S1∩S2/=?,and then continued with|S|=|S1|+|S2|,which is ridiculous.Actually,we think that Guu’s argument works in the sence that one can partition S into two subsets, S1and S2(and thus S1∩S2=?),and then project them into Qn?1to get S′1and S′2,respectively.On the one hand, it may happen that S′1∩S′2/= ?.On the other hand, since the projection preserves the cardinalities of S1and S2, we still reach the conclusion that |S| = |S′1|+|S′2|.After we redefine the two sets, Guu’s argument for the theorem does work.

Although there are some gaps, Guu’s arguments in [6] are as excellent as [2, 8].For completeness, we keep almost all of the arguments of[6].In Section 2,we show some preliminaries,including the cubal, the partition path, the type and the gray code.With the help of the gray code, we can get the formula of θ(n,2n?1,t) for 0 ≤t ≤2n?3.In Section 3, we introduce the Takagi functions, which will help us to define an(x,y).In Section 4,we prove some inequalities,and then prove Theorems 1.2, 1.3 and 1.1.In the Appendix, we list the Mathematica codes that verify the numerical calculations in the proof of Theorem 1.2.

2 Preliminaries

2.1 Cubal

Let us recall the definitions of the subcube and its neighbor in [9].A d-subcube of Qnis induced by the set of all vertices having the same (fixed) values in some n ?d coordinates.A neighbor of a d-subcube of Qnis any d-subcube which differs from the given one in exactly one of the n ?d fixed coordinates.

Take S ?V(Qn) with |S|=k, where we write that

2.2 Partition Path

We define the derived network of the embedding problem as the vertex-weighted graph

where V(D)consists of all subsets of V(Qn)of cardinality 2n?1,and e ∈E(D)with e={U,W},if |U?W|=2, where |U?W|=|UW|+|WU|.The weight of a vertex U ∈V(D) is θ(n,U).

For any U,W ∈V(D), define

We can directly verify that dDis a metric on V(D).

We call a simple path

We say that the partition path F =(F1,F2,···,F2n?1,Fc1) has weight WL(Qn,C2n;ηF).

From the above analysis,there is a one-to-one correspondence between the set of partitions paths and the collection of embeddings.Solving the circular wirelength problem is the same as finding a partition path in the derived network that has a minimum weight.

2.3 The Type

We discuss some properties of the type defined in (1.2).A subset S ?V(Qn) with |S| =2n?1is said to be of small type if 0 ≤Type(S)≤2n?3; otherwise, it is said to be of big type.

For a subset S ?V(Qn) with |S|=k and Type(S)=t, by definition, there is a half plane H ∈Hnsuch that |S ∩H|=t and |S ∩Hc|=k ?t.Let

we have that

Therefore,

This proves the lemma.?

Corollary 2.3Let S ?V(Qn)with|S|=2n?1.If there exists a half plane H ∈Hnsuch that |S ∩H|≤2n?3, then we have that Type(S)=|S ∩H|.

ProofIf |S ∩H|<2n?3, then, by Lemma 2.2,we have that Type(S)=|S ∩H|.Assume that|S ∩H|=2n?3.Suppose that Type(S)<|S ∩H|.Then we have that Type(S)<2n?3.By Lemma 2.2, |S ∩H|>2n?3, which is a contradiction.Thus, we have that Type(S)=|S ∩H|.

?

Corollary 2.4Assume that U,W are neighbors in V(D) and are both of a type strictly smaller than 2n?3.Then there exists a unique half plane H ∈Hnsuch that

ProofBy Lemma 2.2, there exists a unique half plane H such that

Since U, W are neighbors, i.e.|U?W|=2, we have that

By Corollary 2.3, |W ∩H|=Type(W).?

Proposition 2.5([6, Proposition 8]) Let F be a partition path with the type sequence

We have that

(1) for any 1 ≤i<2n?1, |ti?ti+1|≤1;

(2) there exist at least two i with 1 ≤i ≤2n?1such that ti≥2n?3.

Proof(1) We only prove the case i = 1, under the assumption that t1≤t2, since a similar argument works for the other cases.Then there exists a half plane H ∈Hnsuch that

so t2?t1=1 or 0.

(2) We only need to prove that, for any 1 ≤i ≤2n?2, there exists j with i ≤j

This contradicts the fact that dD(Fi,Fi+2n?2)=2n?1.?

2.4 The Gray Code

A gray code is an ordering of 2nbinary numbers such that only one bit changes from one entry to the next; it is also a Hamilton cycle on an n-dimensional hypercube.Each gray code corresponds to an embedding from Qnto C2n.The following embedding ξncorresponds to reflected Gray code: for any x=x1...xn∈{0,1}n,we define the n-tuple y =y1...yn∈{0,1}nby the conditions

Then ξn(x)=(y)2+1, where (y)2is the integer with binary expansion y.

For any 1 ≤i ≤n, define the mappings

such that, for any x1···xn?1∈{0,1}n?1,

3 The Takagi Function

For x ∈[0,1], let

4 Inequalities

Lemma 4.1([6, Claim 11]) For 2n?2≤k ≤2n?1, θ(n,k)≥θ(n,2n?2).

ProofBy Lemma 2.1, θ(n,2n?1) = θ(n,2n?2) = 2n?1.By (3.3), we only need to prove,for n ≥2 and x ∈[1/4,1/2], that mn(x) ≥1/2.It is directly apparent that m2(1/4) =m2(1/2)=1/2.Since m2(x) is linear in the interval [1/4,1/2], m2(x)≡1/2 for x ∈[1/4,1/2].By (3.2), we have that

The following theorem is the exact form we need in the proof, and is a little different from Theorem 13 of [6]:

Theorem 4.2For 0 ≤k ≤2n?1,

ProofWe proceed by induction on n.For n=1 and k =0,1, it can be directly checked that the theorem holds.

Take n>1 and suppose, for 0

For 0 ≤k ≤2n?2, we have that

where the inequality is due to the induction hypothesis.

We only prove the case i=1; we may show the other cases in a similar way.

Proof of Theorem 1.3We proceed by induction on n.The values of θ(n,k,t)for n=5 and k,t satisfying (1.5) are listed in Table 1, and from this we verify directly the theorem for n=5.

Table 1 Comparision of θ(5,k,t) and 25·f(2?5k)

Assume that n ≥6 and that the theorem holds for any m with 5 ≤m< n.We prove the theorem for n.To this end, we take S ?V(Qn) such that |S| = k and Type(S) = t with k,t satisfying (1.5).

Suppose, for any 1 ≤i ≤n, that

Then

Figure 2 Case n=6

Figure 3 Modifications of type sequences for a sample embedding η

where η(v) are listed in the lexicographic order of v ∈{0,1}6.

Appendix

The following are the Mathematica codes to verify (4.10) and (4.11):