数理解析研究所講究録 1222 巻 2001 年 178-188

178
On Linear Arrangement Problems on
Multidimensional Torus Graphs
神保 秀司 (Shuji Jimbo), 橋口 攻三郎 (Kosaburo Hashiguchi), 武藤 仁之 (Hitoshi Muto)

岡山大学工学部 (Faculty of Engineering, Okayama University)

Abstract

Alnear layout of agraph is aone-t0-0ne mapping of the vertices of into theintegers from 1to the number of vertices of . Since the range of alinear layout
over all ofis regarded as the positions on the number line, the sum. For every pair of positive integers
the edges $vw$ is called the sum of edge length
is introduced. The vertex-set of
and $m$ , the -dimensional mTorus graphvalue -dimensional vectors, and the edge-set is the set ofis the set of all
and $w=(w_{1},w_{2}, \ldots,w_{n})$ such that they differ
pairs of vertices $v=$
or
say , and either
at exactly one
is the lnear layout that arranges the vertices inholds. The natural layout oflexicographic order. It is proved that, for every positive integer , the sum of edge
length of the natural layout is the minimum among the ones of all linear layouts of. Furthermore, the set of lnear layouts of whose sum of edge length is the
maximum is completely characterized.
$G$

$G$

$L$

$G$

$\mathrm{o}\mathrm{f}|L(v)-L(w)|$$\mathrm{o}\mathrm{f}L$$r_{m}$$n$$n$$\mathrm{I}_{m}^{m}$$\mathrm{a}1$$\mathrm{Z}_{m}$$\mathrm{n}$$(v_{1},v_{2}, \ldots, v_{n})$$wj\equiv vj+1(\mathrm{m}\mathrm{o}\mathrm{d} m)$$vj\equiv wj+1(\mathrm{m}\mathrm{o}\mathrm{d} m)$$j$$\mathrm{i}\mathrm{n}\mathrm{d}*$$T_{m}^{*}$$n$$T_{3^{\hslash}}$$T_{3^{\hslash}}$Keywords: graph theory, induced subgraph, hypercube, torus, lnear layout.

1Introduction
Alnear layout of agraph $G=(V,E)$ , where $V$ and $E$ are vertex-set and edge set
respectively, is aone-t0-0ne mapping $L:Varrow\{1,2, \ldots, |V|\}$ . If we regard the range of, then places each vertex of at the corresponding
as the positions on anumber,
on the interval between the points
and each edge of
position on the number
corresponding to the end vertices of the edge. We call the value $\sum_{v*u\in B}|L(v)-L(w)|$ thedenote the -dimensional hypercube, or -cube. The
sum of edge length of . Let$V(Q_{n})$, the set of-dimensional0-1 vectors. The,,
isdenotedvertex-set ofedge set of , denoted $E(Q_{n})$ , is the set of dl pairs of vertices $v=(v_{1},v_{2}, \ldots, v_{1}.)$ andis theof$w=$ $(w_{1},w_{2}, \ldots,w_{n})$ that differ at exactly one index. The natural layout
lnear layout defined as$L$$\underline{\mathrm{l}\mathrm{i}\mathrm{n}}\mathrm{e}$

$G$

$L$

$G$

$\underline{1\mathrm{i}\mathrm{n}}\mathrm{e}$$L$$Q_{n}$$n$$Q_{\hslash}$$\{0, 1\}^{n}$

au

$n$

$n$

$Q_{n}$$N_{n}$$N_{n}((x_{1},x_{2}, \ldots,x_{\iota},))=1+\sum_{\Rightarrow 1}^{n}2^{:-1}X:$$Q_{\hslash}$.

in lexicographic order.
arranges theIn other words, the natural layout of
Nakano et al. showed that the sum of edge length of the natural layout of ahypercube is.
always the minimum among the ones of linear layouts of theparalleldeveloping
hypercubesforpropertiesof
It is important to analyze topologicalcomputation technology. Furthermore, when you attempt to encode the RGB data of apicture into binary strings and to transmit them through acommunication channel withthe sum of edge length of thesome transmission error, then you might need to$Q_{n}$$\mathrm{v}.\alpha \mathrm{t}\mathrm{i}\mathrm{c}\mathrm{a}\mathrm{e}$$\mathrm{a}\mathrm{I}$$\mathrm{h}\mathrm{y}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{c}\mathrm{u}\mathrm{b}\mathrm{e}[\mathrm{N}\mathrm{C}\mathrm{M}^{+}90]$$\ovalbox{\tt\small REJECT} \mathrm{e}$179linear layout that corresponds to the encoding. The average change of the picture causedby one bit error in the transmission is expected to be in proportion to the sum of edge
length. If we can use alarger alphabet than the binary one to encoding the RGB dat4
the sum of edge length of thethen it is probably suitable for the transmi ion to
encoding.
corresponds
to
the
that
graph
torus
For every pair of positive integers and $m$ , the -dimensional $m$ torus paph
-valued n-dimensional
is the set of allis defined as follows: The vertex-set of$v=(v_{1},v_{2}, \ldots,v_{n})$pairsvertices
of
the
of
of
all
the
set
vectors, and the edge set is
and $w=$ $(w_{1}, w_{2}, \ldots,w_{n})$ such that they differ at exactly one index, say , and either
holds. The phrase “torus graph” is the
or
$m$
$m$
is the lnear.
The natural layout offorgraphsgeneral notation for -torus
layout that arranges the vertices in lexicographic order. We shall prove that, for every
positive integer , the sum of edge length of the natural layout is the minimum among
the ones of all lnear layouts of . In the proof, we basicaly use the technique of Nakano
et al., and develop it into more elaborated one.
layouts ofthat have
Furthermore, we shall completely characterize the set ofnecessaryThepositive
integer.
arbitrary
an
where
is
length,edge
the maximum sum of
to have the maximum sum of edge lengthand sufficient condition for alnear layoutthat differ at exactly one position of components,
is that, for each triple of vertices ofeach of the three sets of vertices determined by , $A=\{L^{-1}(1),L^{-1}(2), \ldots,L^{-1}(3.|-1)\}$,$B=\{L^{-1}(3^{n-1}+1),L^{-1}(3^{n-1}+2), \ldots,L^{-1}(2\cdot 3^{n-1})\}$, and $C=\{L^{-1}(2\cdot 3^{n-1}+1),L^{-1}(2\cdot$$3^{n-1}+2)$ ,,contains avertex in the triple.
$\ovalbox{\tt\small REJECT} \mathrm{e}$$r_{m}$$n$$n$$\mathrm{Z}_{m}$$T_{m}^{n}$$j$$w_{\mathrm{j}}\equiv v_{j}+1(\mathrm{m}\mathrm{o}\mathrm{d} m)$$v_{j}\equiv w_{j}+1(\mathrm{m}\mathrm{o}\mathrm{d} m)$au$T_{m}^{n}$$n$$T_{3}^{n}$$\underline{1\mathrm{i}\mathrm{n}}\mathrm{e}\mathrm{a}\mathrm{r}$$T_{3}^{n}$$n$$L\mathrm{o}\mathrm{f}T_{3}^{n}$$T_{3}^{n}$$L$$\ldots$$L^{-1}(3^{n})\}$

2Preliminaries. If $G$
The size of afinite set , namely, the number of elements of $S$ , is denoted byis asimple undirected graph, then $V(G)$ and $E(G)$ denote the vertex-set and edge-set ofand asubset of $V(G)$ , $G[S]$ denotes the subgraph of $G$, respectively. For a
induced by .
into
is aonet0-0ne mapping of the vertices of
Alnear layout of agraph$G$$\{1, 2, \ldots, |V(G)|\}$ . Let
,
the
of
where
order
order
agraphbe alnear layout ofof is the number of the vertices of . For each edge $e=vw\in E(G)$ , $L(e)$ denotes
the closed interval $[ \mathrm{n}\cdot \mathrm{n}\{L(v), L(w)\},\max\{L(v),L(w)\}]$ on the number Hue. The sumof edge length of is $\sum_{vw\in B(G)}|L(v)-L(w)|$ . We write the sum of edge length of. For an integer $\in\{1,2, \ldots,n-1\}$ , $C_{G}(L, k)$ denotes the set of edgesas. If the graph designated by the subscript $G$ is clear in{context, then we may leave out the subscript from the notation $C_{G}(L,k)$ . For an integer$\in\{1,2, \ldots,n-1\}$ , $H_{L}(k)$ and $T_{L}(k)$ denote the following two sets of vertices of $G$ ,$\{L^{-1}(1), L^{-1}(2), \ldots,L^{-1}(k)\}$ and $\{L^{-1}(k+1),L^{-1}(k+2), \ldots, L^{-1}(|V(G)|)\}$ , respectively.
By definition, $C_{G}(L, k)$ is the set of all edges that connect avertex in $H_{L}(k)$ and one in, since each edge $vw$
$T_{L}(k)$ . The sum of edge length ofof is equal to. Thus, we conclude the following
contributes $|L(v)-L(w)|$ to the sum
proposition
$|S|$

$S$

$G$

$S$

$\mathrm{g}\dot{\mathrm{r}}\mathrm{a}\mathrm{p}\mathrm{h}G$

$S$

$G$

$G$

$L$

$n$

$G$

$G$

$L$

$L$

$\mathrm{S}EL(L)$$k$$e\in \mathrm{E}(\mathrm{G})|[k, k +1]\subseteq \mathrm{L}(\mathrm{e})$

$G$

$k$

$L$

$G$

$\sum_{=1}^{n-1}.\cdot|C_{G}(L,i)|$$\sum_{=1}^{n-1}.\cdot|C_{G}(L,i)|$

180
Proposition 1Let$L$

be a linear layout of a graph G. Then, the following equation holds:$SEL(L)= \sum_{vw\in B(G)}|L(v)-L(w)|=.\cdot\sum_{=1}^{n-1}|C_{G}(L,i)|$.

be apositive integer. The -dimensional hypercube, or -cube, is anLetare. The vertex-set and edge set ofundirected graph, denoted by,Vn)) $| \sum_{=1}^{n}|x:-y_{}|=1$ }, respectively. Let $x=$,
, ),,and {((
be avertex of . The number of 1’s in the components of , namely,, is said to be the weight of , denoted by $w(x)$ . The function that assigns thevalue:to each $x=$ $(x_{1},x_{2}, \ldots,x_{n})\in V(Q_{n})$ is said to be the natural layout.
of , denoted by
Let be apositive integer and $m$ an integer greater than 2. The -dimensional mis defined in the previous section. The weight of atorus gaph is defined
torus graphcan be uniquely
in asimilar manner to the case for hypercubes. Every element$:\in\{0,1,2,\ldots,m-1\}$. Function
elements,
whererepresented by the sum of :unit
is defined as
:
$n$

$n$

$\mathrm{n}$$Q_{n}$$Q_{n}$$x_{1},x_{2}$$\ldots$$x_{n}$$(y_{1,\mathfrak{R}}$$(x_{1},x_{2}, \ldots,x_{n})$$\{0, 1\}^{n}$$\ldots$$x$$Q_{n}$$x$$\sum_{=1}^{n}X:$$1+ \sum_{=1}^{n}\dot{?}^{-1}X$$N_{1}.(x)$$Q_{\hslash}$

$n$

$n$

$T_{m}^{n}$$z\in \mathrm{Z}_{m}$$\rho_{m}$$\mathrm{Z}_{m}arrow \mathrm{Z}$$=:$$\rho_{m}$,. The sum
be avertex ofwhere $:\in\{0,1,2, \ldots,m-1\}$ . Let $x=$$w(x)$. The function that assigns
is said to be the weight of , denoted by$(x_{1},x_{2}, \ldots,x_{n})\in V(T_{m}^{n})$ is said to be the natural$x=$
the value:to each. We may leave out subscript from the notation $N_{n}(x)$ ,layout of , denoted by
if is clear in context.
$(x_{1},x_{2}, \ldots,x_{r\iota})$$T_{m}^{n}$$x$$\sum_{=1}^{n}\rho_{m}(x:)$$1+ \sum_{=1}^{n}.\cdot 3^{:-1}X$$T_{m}^{n}$$N_{*}.(x)$

$n$

$n$

3The Minimality of the Sum of Edge Length of the
Natural Layouts of Hypercubes

181
Since Q. is an -regular graph, the sum of degrees of al vertices inon L. We, therefore, have$\mathrm{y}\mathrm{g}$$|CQ_{n}(L,i)|=ni-2|E(Q_{\hslash}[H_{\iota}(i)])|$$\mathrm{f}\mathrm{f}\mathrm{z}_{\ovalbox{\tt\small REJECT}}(\mathrm{i})$does not depend.

Thus, it holds that if, for each $i\in\{1,2, \ldots,2^{n}-1\}$ , $|E(Q_{n}[H_{N}(i)])|$ is the maximum
size of asubgraph ofinduced by vertices, then the sum of edge length of $N$ is the
maximum of the sum of edge length of alnear layout of .
Let $f_{n}(k)$ denote the number of edges of the subgraph ofinduced by $H_{N}(k)$ , namely$=|E(Q_{n}[H_{N}(k)])|$ . Since the following proposition holds, we shall therefore leaveout the subscript ffom .
$Q_{n}$$i$$Q_{n}$$Q_{n}$$\mathrm{f}(\mathrm{k})$$n$$f_{n}$

Proposition 2For any positive integers$Q_{n_{1}}[H_{N}(k)]$ is isomorphic to $Q_{n_{2}}[H_{N}(k)]$ .

$n_{1}$,$n_{2}$, and k with $1\leq k\leq 2^{n_{1}}$ and $n_{1}<n_{2}$ ,We have two recursive definition of $f(k)$ . In one definition, asubgraph ofisdecomposed according to the first components of the vertices of the subgraph. We cffi
such decomposition “the first index decomposition.” In the other definition, asubgraphofis decomposed according to the -th components of vertices of the subgraph, whereis the maximum integer such that there are two distinct -th components of the verticesof the subgraph. We
such decomposition “the largest index decomposition.” Therecursive step of the former definition of $f(k)$ is$Q_{n}$$Q_{n}$

$j$

$j$

$j$

$\mathrm{c}\mathrm{a}\mathrm{U}$$f(k)=f(\lfloor k/2\rfloor)+f(\lfloor(k+1)/2\rfloor)+\lfloor k/2\rfloor$,(1)

and the recursive step of the latter one is$f(k)=f(2^{\lceil\log_{2}(k/2)\rceil})+f(k-2^{\Pi \mathrm{o}\mathrm{g}_{2}(k/2)\rceil})+k-2^{\lceil\log_{2}(k/2)\rceil}$.

(2)

Both of the bases of the two definition are the same as$f(0)=f(1)=0$ .

(3)

The following proposition ensure that the expressions above define $f(k)$ correctly.
Proposition 3Let , , and be positive integers with $j\leq n$ and $k<2^{n}$ . Let
anddenote $\{(x_{1},x_{2}, \ldots,x_{n})\in H_{N}(k)|x_{j}=0\}$ and $\{(\overline{x}_{1},x_{2}, \ldots,x_{n})\in H_{N}(k)|x_{j}=1\}$,
respectively. Then, induced subgraphs
andare isomorphic to $Q_{n}[H_{N}(|S_{0}|)]$$Q_{n}[H_{N}(|S_{1}|)]$
and, respectively.
$n$

$j$

$k$

$S_{0}$$S_{1}$$Q_{n}[S_{0}]$$Q_{n}[S_{1}]$Let $g(k)$ denote the function ffom non-negative integers to non-negative integers recursively defined by$g(0)=g(1)=0$ ,and$g(k)= \max_{1\leq\leq k/2}\{g(i)+g(n-i)+i\}$.

182
Then, it follows from the definitions of that, for all $\in\{0,1, \ldots,2^{n}\}$ , the size of every
subgraph ofwhose order is is not greater than $g(k)$ . The reason is as follows.
Every non-null subgraph ofinduced by can be decomposed into three parts bypartitioning intoandand . Two of the three parts are subgraphs induced by, respectively, and the other part is the set of edges that connect avertex in and one
and is performed according to the -th components
in . The partition of intoof the vertices, where is determined by aparticular edge $e=vw$ of . By definition,and have only one position at which the components of and are different. We
partition intoandso that the -th component of each vertex in is for both$:\in\{0,1\}$ . Then, the number of edges that connect avertex in
and one inis theand .
size of the smaller one in$f(k)$
In fact, the function
coincides with $g(k)$ for every non-negative integer . Nakano
et al. proved the fact by induction on , where the induction hypothesis is $f(k)\geq g(k)$ .
Notice that $f(k)\geq g(k)$ is equivalent to $f(k)=g(k)$ by definition. It holds that the size
is not greater than $f(|V(H)|)$ . This statement seems to be tooof any subgraph $H$ of
weak for the induction hypothesis, although it is directly necessary for the proof.
Nakano et al. decomposed $Q_{n}[H_{N}(k)]$ by the first index decomposition, and employed
expression (1) in the definition of $f(k)$ . However, their selection of the decomposition
method seems not to be essential to the proof, since we can complete the proof by employing the largest index decomposition[M0u96, HMJ99]. We omit the detailed story
reluctantly.
$k$

$g$

$k$

$Q_{n}$$G$$S$$S_{0}$$S$$Q_{n}$$S_{1}$$S_{0}$$S_{0}$$S_{1}$$S$$S_{1}$$S_{0}$$j$$S_{1}$

$G$

$j$

$j$

$w$

$v$

$S$

$S_{0}$$w$$v$$S_{}$$j$$S_{1}$$i$$S_{0}$$S_{0}$$S_{1}$$S_{1}$$k$$k$$Q_{n}$

4The Minimality of the Sum of Edge Length of the
Natural Layouts of Torus Graphs
In this section, we shall show briefly that the sum of edge length of the natural layout of
a3- orus gaph is the maximum of the sum of edge length of of the lnear layouts of
the 3-torus gaph.
$\mathrm{a}\mathrm{I}$

Theorem 4Let
holds

$n$

be an integer greater than or equal to 2. Then, the following equation$SEL(N_{n})=\dot{\mathrm{m}}\mathrm{n}SEL(L)L\in \mathrm{L}$ ’where$T_{3}^{n}$.

$N_{n}$

denotes the natural layout$ofT_{3}^{n}$and$\mathcal{L}_{n}$denotes the set of all linear layouts of

The outlne of the proof of Theorem 4advances in almost parallel with the proof for
hypercubes.
By an argument similar to the corresponding one in the previous section, in which
Proposition 1and the fact thatis $2n$-regulg graph are used, we have that the following
lemma is sufficient to prove Theorem 4. Notice that $H_{N}(:)=\{N^{-1}(1),N^{-1}(2), \ldots,N^{-1}(i)\}$is defined in Section 2.
$T_{3}^{n}$

183
Lemma 5For each $i\in 1,2$ , $\ldots.’ 3^{n}-1$ ,$|E(T_{3}^{n}[H_{N}(:)])|= \max|E(T_{3}^{*}[H])|H$ ’where $H$ in the right-hand side of the equation above ranges over all of the subsets ofwhose size is .
$i$

$V(T_{3}^{n})=\mathrm{Z}_{3}^{n}$

The following lemmas can be proved easily. We omit the prooffi reluctantly.

Lemma 6For any positive integers
is isovwrphic to$T_{3}^{n_{1}}[H_{N}(k)]$$n_{1}$$T_{3}^{n_{2}}[H_{N}(k)]$,$n_{2}$

.

, and

$k$

$with$$1\leq k\leq 3^{n_{1}}$and $n_{1}<n_{2}$ ,Lemma 7Let be a positive integer. Let be a positive integer less than or equal to, and a positive integer less than . Let, anddenote $\{(x_{1},x_{2}, \ldots,x_{n})\in$$\{(x_{1},x_{2},\ldots,x_{n})\in
H_{N}(k)|x_{\mathrm{j}}=1\}$$H_{N}(k)|x_{j}=0\}$ ,, and $\{(x_{1},x_{2}, \ldots,x_{n})\in H_{N}(k)|x_{\mathrm{j}}=$, respectively. Then, induced subgraphs,, and
are isomorphic to,, and, respectively.
$n$

$j$

$k$

$n$

$3^{n}$$2\}$$S_{0},$$T_{3}[S_{0}]$$T_{3}^{n}[H_{N}(|S_{0}|)]$$T_{3}^{n}[H_{N}(|S_{1}|)]$$S_{1}$$S_{2}$$P_{3}[S_{1}]$$T_{3}^{n}[S_{2}]$$T_{3}^{n}[H_{N}(|S_{2}|)]$

Let $f(k)$ denote $|E(T_{3}^{n}[H_{N}(k)])|$ for arbitrary geater than 1. By Lemma 6, thevalue $|E(T_{3}^{n}[H_{N}(k)])|$ does not depend on . By observing that, for any distinct and ,any two edges and e2 ofthat connect avertex in $H_{N}(|S_{}|)$ and one inarenot adjacent, we have arecursive definition of $f(k)$ as follows:
$n$

$n$

$i$

$H_{N}(|S_{\mathrm{j}}|)]$$T_{3}^{n}$$e_{1}$$j$$f(0)=f(1)=0$ , $f(2)=1$ ,

(4)

and
$f(k)=f( \lfloor\frac{k}{3}\rfloor)+f($ $\lfloor\frac{k+1}{3}\rfloor)+f($ $\lfloor\frac{k+2}{3}\rfloor)+2\lfloor\frac{k}{3}\rfloor+\lfloor\frac{k+1}{3}\rfloor$.

(5)

The following lemma can be proved easily. We omit the proof.

Lemma 8Let , , , and
$b$

$a$

a

$k$

$c$

$=\lfloor k/3\rfloor$,

be non-negative integers. Then,b $=\lfloor(k+1)/3\rfloor$ ,and c $=\lfloor(k+2)/3\rfloor$ ,if and only if
k $=a+b+c$ and a $\leq b\leq c\leq a+1$ .

Let $g(k)$ denote the function from non-negative integers to non-negative integers recursively defined by$g(0)=g(1)=0,g(2)=1$ ,

(6)

and
$g(k)= \max_{h,,\dot{1}\mathrm{j}}\{g(h)+g(i)+g(j)+2h+i\}$,(7)

where , , and range over the integers with $0\leq h\leq i\leq j\leq k-1$ and $h+:+j=k$ .
By an argument similar to the corresponding one in the previous section, we have that,for all $k\in\{1,2, \ldots,3^{n}\}$ , the size of every subgraph ofwhose order is is not geaterthan $g(k)$ .
The following lemma is the core of the proof of Theorem 4.
$h$

$i$

$j$

$T_{3}^{n}$

$k$

184
Lemma 9Let k be a positive integer. Let

and$\mathrm{h}_{\mathrm{O}\mathrm{t}}h_{\mathrm{I}\mathrm{j}}h_{2t}\mathrm{j}_{\ovalbox{\tt\small REJECT} \mathrm{Q}_{\mathrm{t}}}\mathrm{i}_{1\mathrm{y}}\mathrm{j}_{\ovalbox{\tt\small REJECT} 2\mathrm{p}}:\ovalbox{\tt\small REJECT} \mathrm{o}_{\mathrm{t}}\mathrm{j}_{1\mathrm{z}}$negative integers. If$4\leq h_{1}\leq h_{2}\leq h_{0}+1$,$i_{0}\leq i_{1}\leq i_{2}$$\leq i_{0}+1$,$j_{Z}$$j_{0}\leq j_{1}\leq j_{2}\leq j_{0}+1$$h_{0}+h_{1}+h_{2}\leq i_{0}+i_{1}+i_{2}\leq j_{0}+j_{1}+j_{2}<k$be non-,,and$h_{0}+h_{1}+h_{2}+i_{0}+i_{1}+i_{2}+j_{0}+j_{1}+j_{2}=k$then$he|\epsilon$

exist nine integers$h_{0}’$,$h_{1}’$$(f4’,h_{1}’,h_{2}’,i_{0}’,i_{1}’,i_{2}’,j_{0}’,j_{1}’,j_{2}’)$$4\leq i_{0}’\leq j_{0}’$,$h_{2}’,$$i_{0}’,\dot{\iota}_{1}’$,$i_{2}’$,$j_{0}’$,$j_{1}’$

is a pemutation of,$h_{1}’\leq\dot{l}_{1}’\leq j_{1}’$

,

, and

$j_{2}’$,

such that$(h_{0},h_{1}, h_{2},i_{0},i_{1},i_{2},j_{0},j_{1},j_{2})$$h_{2}’.\leq i_{2}’\leq j_{2}’$,,,$h_{0}’+\dot{\iota}_{0}’+j_{0}’\leq h_{1}’+i_{1}’+j_{1}’\leq h_{2}’+\dot{\iota}_{2}’+j_{2}’\leq h_{0}’+i_{0}’+j_{0}’+1$

and$4h$ $+3h_{1}+2h_{2}+3\dot{\eta}+2:_{1}+:_{2}+2j\mathrm{o}+j_{1}\leq 4h_{0}’+3h_{1}’+2h_{2}’+3i_{0}’+2i_{1}’+i_{2}’+2j_{0}’+j_{1}’$ .

Proof.

Assume that the nine components satisfy the premise of the lemma. If $h_{0}+$holds, then set the nine variables with aprime mark as$h_{0}’=b’$
,
,
,
,
,
,
, and
. Then, the conclusion of the lemma holds. In what follows, we, therefore, assume that$h_{1}+h_{2}=\dot{\eta}+:_{1}+:_{2}=jo+j_{1}+j_{2}$’$\dot{\iota}_{0}’=h_{1}$$j_{0}’=h_{2}$$h_{1}’=i_{0}$$i_{1}’=:_{1}$$j_{1}’=i_{2}$$h_{2}’=j_{0}$$i_{2}’=j_{1}$$j_{2}’=$$j_{2}$b$+h_{1}+h_{2}\neq\dot{\mathrm{b}}+i_{1}+\dot{|}2$holds.

Given a3
as foUows:$\mathrm{x}$$3$matrlx

$A$

or

(8)

$i\mathrm{p}+:_{1}+i_{2}.\neq j_{0}+j_{1}+j_{2}$, we define four positive integers $x_{0}(A)$ , $x_{1}(A)$ ,.

$x_{0}(A)= \mathrm{m}\mathrm{x}\{:\in\{1,2,3\}|\sum_{\mathrm{j}=1}^{3}A(:,\mathrm{j})=\mathrm{m}\mathrm{i}$$y_{0}(A)$, and $y_{1}(A)$$\{\sum_{j=1}^{3}A(k,j)|k\in\{1,2,3\}\}$,,$x_{1}(A)= \mathrm{m}\dot{\mathrm{m}}\{:\in\{1,2,3\}|\sum_{j=1}^{3}A(:,j)=\mathrm{m}\alpha\{\sum_{j=1}^{3}A(k,j)|k\in\{1,2,3\}\}$$y_{1}(A)=\mathrm{m}\mathrm{x}\{\mathrm{j} \in\{1,2,3\}|A(x_{0}(A),j)<A(x_{1}(A),j)\}$,and$y_{0}(A)=\mathrm{m}\dot{\mathrm{m}}\{j\in\{1,2,3\}|A(x_{1}(A),j)=A(x_{1}(A),y_{1}(A))\}$.

185
Moreover, for two pairs of integers $(i,j)$ and $(i’,j’)$ whose components are all belong tomatrix obtained by swapping the $(i,j)$ and{1, 2, 3}, let $A[(i,j), (i’,j’)]$ denote the 3$(i’,j’)$ components of $A$ , that is,$\mathrm{x}3$$A[(i,j), (i’,j’)](i,j)=A(i’,j’),A[(i,j), (i’,j’)](i’;j’)=A(i,j)$ ,and if $(x, y)\neq(i,j)$ and $(x,y)\neq(i’,j’)$ then$A[(i,j), (i’,j’)](x,y)=A(x,y)$ .
Furthermore, $P(A)$ denote the following property of 3$\mathrm{x}3$matrix$A$:

for each i $\in\{1,2,$ 3} and$A(i, 1)\leq A(i,2)\leq A(i,3)$$A(1,1)+A(1,2)+A(1,3)\leq A(2,1)+A(2,2)+A(2,3)\leq A(3,1)+A(3,2)+A(3,3)$ .

We define functions Aand$\mu$both defined on$3\cross 3$

matrices as$\lambda(A)=A(3,1)+A(3,2)+A(3,3)-A(1,1)-A(1,2)-A(1,3)$

and$\mu(A)=4A(1,1)+3(A(1,2)+A(2,1))+2(A(1,3)+A(2,2)+A(3,1))+A(2,3)+A(3,2)$ .

Let $M$ denote the$3\cross 3$$M(1,1)=h_{0}$ ,matrix defined by$M(1,3)=j_{0}$ ,$M(1,2)=i_{0}$ ,$M(2,3)=j_{1}$ ,A $(3, 1)=h_{2}$ ,$M(2,1)=h_{1}$ ,$M(3,2)=i_{2}$ ,and$M(2,2)=i_{1}$ ,$M(3,3)=j_{2}$ .

Notice that the premise of the lemma implies that $P(M)$ holds.
At this point, we are ready to describe the permutation of the components of$M$ that brings values assigned to the nine variables with aprime mark.
We de$M’$$\lambda(M)\leq
1$
Otherwise,
,
.
then
let
$M’=M$
as follows. If
fine matrix
denote $M[(x_{0}(M),y_{1}(M)), (x_{1}(M),y_{0}(M))]$ . If $\lambda(M)=2$ , then $M’=M_{1}$ . 0th$=3$ , then, $M’=M_{1}[(x_{0}(M_{1}),y_{1}(M_{1})), (x_{1}(M_{1}),y_{0}(M_{1}))]$ .
In
erwise,.
$P(A)$
2,that
weobserve
and
with
any
matrixgeneral, for
3$P(A[(x_{0}(A),y_{1}(A)), (x_{1}(A),y_{0}(A))])$ , $\lambda(A[(x_{0}(A),y_{1}(A)), (x_{1}(A),y_{0}(A))])\leq\lambda(A)-1$ , and$\mu(A[(x_{0}(A),y_{1}(A)), (x_{1}(A),y_{0}(A))])\geq\mu(A)$ hold. Thus, we have $P(M’)$ , $\lambda(M’)\leq 1$ , and$\mu(M)\leq\mu(M’)$ in any case. The following setting of the nine variables with aprime marksatisfies the conclusion of the lemma:$M_{1}$$\mathrm{i}.\mathrm{e}$$\lambda(\mathrm{A})$$\mathrm{x}3$$h_{0}’=M’(1,1)$ ,$i_{0}’=M’(1,2)$ ,$A$$\lambda(A)$$j_{0}’=M’(1,3)$ ,$j_{1}’=M’(2,3),h_{2}’=M’(3,1)$ ,$\geq$$h_{1}’=M’(2,1)$ ,$i_{1}’=M’(2,2)$ ,and.

$i_{2}’=M’(3,2)$ ,$j_{2}’=M’(3,3)$

We have thus proved the lemma.
$\square$

The following lemma is sufficient to prove Lemma 5. Thus, we conclude that Theorem 4

186
Lemma 10 For every , $f(k)=$. $g(k)$ .
$k$Proof. We prove the lemma by induction on . The base clearly holds. Let be an
integer greater than 2. Assume that $f(l)=g(l)$ holds for all non-negative integers 1lessthan . Let , :, and be integers such that $0\leq h\leq i\leq j\leq k-1$ , $h+i+j=k$ , and$g(k)=g(h)+g(i)+g(j)+2h+i=f(h)+f(i)+f(j)+2h+i$. For $l\in\{0,1,2\}$ , let, respectively. Then,, and,, , and denote integers
we have the following sequence of equations by the definitions of and , the induction
hypothesis, and Lemma 9.
$k$

$k$

$h_{l}$$h$$i_{l}$$k$$j$$\lfloor(h+l)/3\rfloor$$j_{l}$$\lfloor(i+l)/3\rfloor$$\lfloor(j+l)/3\rfloor$$f$$g(k)$$=$$g$$f(h_{0})+f(i_{0})+f(j_{0})+2h_{0}+i_{0}+f(h_{1})+f(i_{1})+f(j_{1})+2h_{1}+i_{1}$$+f(h_{2})+f(i_{2})+f(j_{2})+2h_{2}+:_{2}+2h_{0}+2i_{0}+2j\mathrm{o}+h_{1}+i_{1}+j_{1}$$=g(h_{0})+g(i_{0})+g(j_{0})+g(h_{1})+g(i_{1})+g(j_{1})+g(h_{2})+g(i_{2})+g(j_{2})$$+4h_{0}+3h_{1}+2h_{2}+3i\mathrm{p}+2i_{1}+i_{2}+2j\mathrm{o}+j_{1}$$\leq g(h_{0}’)+g(i_{0}’)+g(j_{0}’)+g(h_{1}’)+g(i_{1}’)+g(j_{1}’)+g(h_{2}’)+g(i_{2}’)+g(j_{2}’)$$+4h_{0}’+3h_{1}’+2h_{2}’+3i_{0}’+2\dot{\iota}_{1}’+i_{2}’+2j_{0}’+j_{1}’$$\leq g(h_{0}’+i_{0}’+j_{0}’)+g(h_{1}’+\dot{\iota}_{1}’+j_{1}’)+g(h_{2}’+i_{2}’+j_{2}’)$$+2(h_{0}’+i_{0}’+j_{0}’)+h_{1}’+\dot{l}_{1}’+j_{1}’$$=$$f(h_{0}’+i_{0}’+j_{0}’)+f(h_{1}’+\dot{\iota}_{1}’+j_{1}’)$$+f(h_{2}’+i_{2}’+j_{2}’)+2(h_{0}’+i_{0}’+j_{0}’)+h_{1}’+i_{1}’+j_{1}’$$=$$f(h_{0}’+i_{0}’+j_{0}’+h_{1}’+\dot{\iota}_{1}’+j_{1}’+h_{2}’+\dot{\iota}_{2}’+j_{2}’)=f(k)$We have thus proved the lemma.

.

$\square$5Linear Layouts of Torus Graphs that Maximize theSum of Edge Lengthdeand an integer $j\in\{1,2, \ldots,n\}$ ,For avertex $x=$
. ofinduced by $\{(y_{1},y_{2}, \ldots,y_{n})\in \mathrm{Z}_{3}^{n}|y_{1}=x_{1},y_{2}=$notes the triangle subgraph of, $y_{n}=x_{1},$ }. Notice that the edge-set of,, $y_{j-1}=x_{j-1},y_{j+1}=x_{j+1}$ ,can bepartitioned into $n3^{n-1}$ such triangles.
$(x_{1},x_{2}, \ldots,x_{n})$$\Delta(x,j)$$T_{3}^{\hslash}$$\mu_{3}$$x_{2}$$\Gamma_{3}$$\ldots$$\ldots$

Theorem 11 Let be a positive integer. A linear layout of
maximizes the sum ofedge length if and only if, for all $x\in V(T_{3}^{n})$ and all $j\in\{1,2, \ldots,n\}$ ,
$n$

$L$

$T_{3^{\hslash}}$,(9)$V(\Delta(x,j))\cap\{L^{-1}(1),L^{-1}(2), \ldots,L^{-1}(3^{n-1})\}\neq\emptyset$

,

(10)

$V(\Delta(x,j))\cap\{L^{-1}(3^{n-1}+1),L^{-1}(3^{n-1}+2), \ldots,L^{-1}(2\cdot 3^{n-1})\}\neq\emptyset$

and$V(\Delta(x,j))\cap\{L^{-1}(2\cdot 3^{n-1}+1),L^{-1}(2\cdot 3^{n-1}+2), \ldots,L^{-1}(3^{l}’)\}\neq\emptyset$

.

(10)

187
denote $\{L^{-1}(1),L^{-1}(2), \ldots,L^{-1}(3^{n-1})\}$ , $\{L^{-1}(3^{n-1}+$$1),L^{-1}(3^{n-1}+2)$ ,, and $\{L^{-1}(2\cdot 3^{n-1}+1),L^{-1}(2\cdot 3^{n-1}+2), \ldots,L^{-1}(3^{n})\}$ ,,respectively. We show that maximizes $|C(L,k)|$ for ffl $k\in\{1,2, \ldots,3^{n}-1\}$ if and onlyintersects ffi of the triangles.
if each of $Xl$ , , and,. We readily have that $|C(L,k)|$ is not greater
Let be an integer in 1, 2,
than the sum of degree of the vertices in $\{L^{-1}(1),L^{-1}(2), \ldots,L^{-1}(k)\}$ . We also havethat all of the edges incident to avertex in $\{L^{-1}(1),L^{-1}(2), \ldots,L^{-1}(k)\}$ contribute 1to,$|C(L, k)|$ if and only if, for every triangle
contains exactly one vertex of . We,
if and only if, forin 1, 2,
therefore have that maximizes $|C(L,k)|$ formanner, we also
asymmetricA.
Inofexactlyvertexone
contains
every triangle ,have that mnimizae $|C(L, k)|$ for all in $\{2 \cdot 3^{n-1},2\cdot 3^{n-1}+1,2\cdot 3^{n-1}+2, \ldots,3^{n}-1\}$
contains exactly one vertex of A.
if and only if, for every triangle ,at most 2to $|C(L, k)|$ . We also havecontributes
anytriangle
We readily have that
if the triangle intersects boththat atriangle contributes 2to $|C(L,k)|$ for every
and .
ofThus, we conclude that the lemma holds.
For example, the three conditions below imply conditions (9), (10), and (11):Let

Proof.

$X_{L}$,$\mathrm{Y}_{L}$, and$Z_{L}$$L^{-1}(2\cdot 3^{n-\mathrm{I}})\}$$\ldots$$L$$Z_{L}$$\mathrm{Y}_{L}$

$k$

$\{$

$3^{n-1}\}$$\ldots$$\Delta$$L$$\Delta$$\Delta$$X_{L}$$\mathrm{a}\mathbb{I}$

$k$

$\{$

$\ldots$$3^{n-1}\}$$X_{L}$$k$$L$$\Delta$$Z_{L}$$k\in \mathrm{Y}_{L}$$X_{L}$$Z_{L}$$\square$$(\forall x\in X_{L})(\forall y\in X_{L})(w(x)\equiv w(y) (\mathrm{m}\mathrm{o}\mathrm{d} 3))$$(\forall x\in \mathrm{Y}_{L})(\forall y\in \mathrm{Y}_{L})(w(x)\equiv w(y) (\mathrm{m}\mathrm{o}\mathrm{d} 3))$

(12)

,

(13)

,

and
$(\forall x\in Z_{L})(\forall y\in Z_{L})(w(x)\equiv w(y) (\mathrm{m}\mathrm{o}\mathrm{d} 3))$

.

(14)

However, we can find alarge number of linear layouts that mnimizae the sum of edge
thelength and that does not satisfy the three conditions above, since if$j\in$
mak
可品\acutees
every
for
length
edge
of
the
sum
also
sum of edge length, then$\{1,2, \ldots, n\}$ and for every
with $a\neq b$ , where $L\mathrm{o}\varphi j[a,b](v)=L(\varphi j[a,b](v))$
and in,is defined as follows: forand function$L\ovalbox{\tt\small REJECT} \mathrm{e}\mathrm{s}$$L\circ\varphi_{\mathrm{j}}[a, b]$

$a$

$b$

$\mathrm{Z}_{3}$$x=(x_{1},x_{2}, \ldots,x_{n})\in \mathrm{Z}_{3}^{*}.$$\varphi_{j}[a,b]$$\varphi_{j}[a,b](x)=(x_{1}, \ldots,x_{j-1},b,x_{j+1}, \ldots,x_{n})$if $xj=a$ ,$\varphi_{\mathrm{j}}[a,b](x)=(x_{1}, \ldots,x_{j-1},a,x_{\mathrm{j}\dagger 1}, \ldots,x_{n})$ifandFor example, let$L$$\varphi_{j}[a,b](x)=x$

denote the lnear layout of$T_{3}^{2}$$x_{\mathrm{j}}=b$,otherwise.

defined by$L((0,0))=2$ , $L((1,0))=4$ , $L((2,0))=9$ , $L((0,1))=5$ , $L((1,1))=8$ ,$L((2,1))=1$ , $L((0,2))=7$ , $L((1,2))=3$ , $L((2,2))=6$ .

Then, $L’=L\circ\varphi_{2}[0,2]$ is described by$L’((0,0))=7$ , $L’((1,0))=3$ , $L’((2,0))=6$ , $L’((0,1))=5$ , $L’((1,1))=8$ ,$L’((2,1))=1$ , $L’((0,2))=2$ , $L’((1,2))=4$ , $L’((2,2))=9$ .

the sum of edge length, since satisfies the three condiLinear layout
tions (12), (13), and (14). Furthermore, lnear layout $L’$ also maximize the sum of edge
length, although $L’$ satisfies none of the conditions (12), (13), and (14).
$L\ovalbox{\tt\small REJECT} es$

$L$

188
6Concluding Remarks
Let

induced by $\{(0,0), (1,0), (1,1), (0,1)\}$ . Since
and $|E(T_{5}^{2}[G])|=4$ , we cannot
replace 3’s in Lemma 5with 5’s. However, we conjecture that the 3’s in Lemma 5can be
replaced with .
$G$denote the subgraph of$T_{5}^{2}$$|E(T_{5}^{2}[H_{N}(4)])|=|E(T_{5}^{2}[\{(0,0), (1,0), (2,0), (3,0)\}])|=3$$4’ \mathrm{s}$References[HMJ99]Kosaburo Hashiguchi, Shintaro Mouri, and Shuji Jimbo. Binary distancecodes. In Algebraic Engineering, pages. World Scientific, 1999.
$2\mathfrak{X}-259$[MOu96]$[\mathrm{N}\mathrm{C}\mathrm{M}^{+}90]$

Mouri. Binary distance codes. Master’s thesis, Okayama University,
1996. Written in Japanese.

$\mathrm{S}\underline{\mathrm{h}\mathrm{i}\mathrm{n}}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{o}$Koji Nakano, Wei Chen, Toshimitsu Masuzawa, Ken’ichi Hagihara, andNobuki Tokura. Cut width and bisection width of hypercube graph. The, 1999.
of IEICE, J73$I\}unsact_{\dot{1}}ons$$\mathrm{A}(4):856\mathrm{k}862$