The Manhattan product of digraphs

The Manha an P oduc o Dig aphs ∗
F. Comellas, C. Dal ´o, M.A. Fiol
Depa amen de Ma em`a ica Aplicada IV
Uni e si a Poli `ecnica de Ca alunya
{comellas,cdal o, iol}@ma4.upc.edu
Janua y 30, 2008
Abs ac
We gi e a o mal de ini ion o a new p oduc o bipa i e dig aphs, he Manha -
an p oduc , and we s udy some o i s main p ope ies. I is shown ha i all he
ac o s o he abo e p oduc a e (di ec ed) cycles, hen he dig aph ob ained is he
Manha an s ee ne wo k. To his espec , i is p o ed ha many p ope ies o hese
ne wo ks, such as high symme ies and he p esence o Hamil onian cycles, a e sha ed
by he Manha an p oduc o some dig aphs. Mo eo e , we p o e ha he Manha an
p oduc o wo Manha an s ee s ne wo ks is also a Manha an s ee ne wo k. Also,
some necessa y condi ions o he Manha an p oduc o wo Cayley dig aphs o be
again a Cayley dig aph a e gi en.
1 In oduc ion
The 2-dimensional Manha an s ee ne wo k M2was in oduced simul aneously, in di -
e en con ex s, by Mo illo e al. [9] and Maxemchuk [8] as an unidi ec ional egula mesh
s uc u e esembling locally he opology o he a enues and s ee s o Manha an (o
l’Eixample in down own Ba celona). In ac , M2has a na u al embedding in he o us
and i has been ex ensi ely s udied in he li e a u e as a model o in e connec ion ne -
wo ks. Fo ins ance, i s a e age dis ance has been compu ed by Khasnabish [7] and Chung
and Ag awal [3], he gene a ion o ou ing schemes by Maxemchuk [8]. Mo eo e , Chung
and Ag awal [3] ga e i s diame e . Va a igos [10] e alua ed again he mean in e nodal
dis ance and p o ided a sho es pa h ou ing algo ism and some Hamil onian p ope ies.
Recall ha a dig aph G= (V, A) consis s o a se o e ices V, oge he wi h a se o
a cs A, which a e o de ed pai s o e ices, A⊂V×V={(u, ) : u, ∈V}. An a c (u, )
is usually depic ed as an a ow wi h ail u(ini ial e ex) and head (end e ex), ha
is, u→ . The indeg ee δ−(u) ( espec i ely, ou deg ee δ+(u)) o a e ex uis he numbe
o a cs wi h ail ( espec i ely, head) u. Then Gis δ- egula when δ−(u) = δ+(u) = δ
o e e y e ex u∈V. Gi en a dig aph G= (V, A), i s con e se dig aph G= (V, A)
is ob ained om Gby e e sing all he o ien a ions o he a cs in A, ha is, (u, )∈A
i and only i ( , u)∈A. The s anda d de ini ions and basic esul s abou g aphs and
dig aphs no de ined he e can be ound in [1, 2, 11].
In his pape , we i s ecall he de ini ion and some o he p ope ies o he Manha an
s ee ne wo k (whe e he Manha an p oduc akes i s name om). A e wa ds we in o-
duce he Manha an p oduc o (bipa i e) dig aphs. I is shown ha when all he ac o s
∗Resea ch suppo ed by he Minis e io de Educaci´on y Ciencia, Spain, and he Eu opean Regional
De elopmen Fund unde p ojec s MTM2005-08990-C02-01 and TEC2005-03575 and by he Ca alan Re-
sea ch Council unde p ojec 2005SGR00256.
1
a e (di ec ed) cycles, hen he ob ained dig aph is jus he Manha an s ee ne wo k.
Mo eo e , we p o e ha he Manha an p oduc o wo Manha an s ee s ne wo ks is
also a Manha an s ee ne wo k. I is p o ed ha many p ope ies o hese ne wo ks,
such as high symme ies and he p esence o Hamil onian cycles, a e sha ed by he Man-
ha an p oduc o some dig aphs. We also in es iga e when he Manha an p oduc o
wo Cayley dig aph is again a Cayley dig aph and cha ac e ize he co esponding g oup.
2 Manha an s ee ne wo ks
In his sec ion, we ecall he de ini ion and some basic p ope ies [4, 5] o a class o o oidal
di ec ed ne wo ks, commonly known as Manha an s ee ne wo ks.
Gi en ne en posi i e in ege s N1, N2,...,Nn, he n-dimensional Manha an s ee
ne wo k Mn=M(N1, N2,...,Nn) is a dig aph wi h e ex se V(Mn) = ZN1×ZN2×
· · · × ZNn. Thus, each o i s e ices is ep esen ed by an n- ec o u= (u1, u2,...,un),
wi h 0 ≤ui≤Ni−1, i= 1,2,...,n. The a c se A(Mn) is de ined by he ollowing
adjacencies (he e called i-a cs):
(u1,...,ui,...,un)→(u1,...,ui+ (−1)
P
j6=iuj,...,un) (1 ≤i≤n).(1)
The e o e, Mnis an n- egula dig aph on N=Qn
i=1 Ni e ices.
The p ope ies o Mna e he ollowing:
•Homomo phism: The e exis an homomo phism om Mn o he symme ic dig aph
o he hype cube Q∗
n, so ha Mnis bo h 2n-pa i e and bipa i e dig aph.
•Ve ex-symme y: The n-dimensional Manha an s ee ne wo k Mnis a e ex-
symme ic dig aph.
•Line dig aph: Fo any N1, N2, he 2-dim Manha an s ee ne wo k M2(N1, N2) is
a line dig aph.
•Diame e : Fo Ni>4, he diame e o he n-dim Manha an s ee ne wo k
Mn=M(N1, N2,...,Nn), i= 1,2,...,n, is
(a)D(Mn) = 1
2Pn
i=1 Ni+ 1, i Ni≡0 (mod 4) o any 1 ≤i≤n;
(b)D(Mn) = 1
2Pn
i=1 Ni, o he wise.
•Hamil onici y: The n-dimensional Manha an s ee ne wo k Mnis Hamil onian.
3 The Manha an p oduc and i s basic p ope ies
In his sec ion, we p esen an ope a ion on (bipa i e) dig aphs which, as a pa icula
case, gi es ise o a Manha an s ee ne wo k. Wi h his aim, le Gi= (Vi, Ai) be n
bipa i e dig aphs wi h independen se s Vi=Vi0∪Vi1,Ni=|Vi|,i= 1,2,...,n. Le π
be he cha ac e is ic unc ion o Vi1⊂Vi o any i; ha is,
π(u) = 0 i u∈Vi0,
1 i u∈Vi1.
Then, he Manha an p oduc Mn=G1k≡ G2k≡ · · · k≡ Gnis he dig aph wi h e ex se
V(Mn) = V1×V2× · · · × Vn, and each e ex (u1,...,ui,...,un) is adjacen o e ices
(u1, . . . , i,...,un), 1 ≤i≤n, when
2
01
2
34
5
0
1
(0,0) (1,0)
(2,0)
(3,0)
(4,0)
(5,0)
(0,1) (1,1)
(2,1)
(3,1)
(4,1)
(5,1)
Figu e 1: The Manha an p oduc Cay(Z6,{1,3})k≡K∗
2(undi ec ed lines s and o pai s
o a cs in opposi e di ec ions).
• i∈Γ+(ui) i Pj6=iπ(uj) is e en,
• i∈Γ−(ui) i Pj6=iπ(uj) is odd.
Fig. 1 shows an example o he Manha an p oduc o he ci culan dig aph on 6
e ices and s eps 1 and 3 (in o he wo ds, he Cayley dig aph on Z6wi h gene a ing se
{1,3}) by he symme ic comple e dig aph on 2 e ices, K∗
2.
Thus, i e e y Giis δi- egula , hen Mnis a δ- egula dig aph, wi h δ=Pn
i=1 δi, on
N=Qn
i=1 Ni e ices.
Some o he basic p ope ies o he Manha an p oduc , which a e a gene aliza ion o
he p ope ies o he Manha an s ee ne wo ks gi en in [4], a e p esen ed in he ollowing
p oposi ion:
P oposi ion 3.1. The Manha an p oduc H=G1k≡G2k≡· · · k≡Gnsa is ies he ollowing
p ope ies:
(a)The Manha an p oduc holds he associa i e and commu a i e p ope ies.
(b)The e exis s an homomo phism om H o he symme ic dig aph o he hype cube
Q∗
n. The e o e, His a bipa i e and 2n-pa i e dig aph.
(c)Fo any n−k ixed e ices xi∈Vi,i=k+ 1, k + 2,...,n, he subdig aph o H
induced by he e ices (u1, u2,...,uk, xk+1,...,xn)is ei he he Manha an p oduc
Hk=G1k≡G2k≡· · · k≡ Gko i s con e se Hk, depending on i α:= Pn
i=k+1 π(xi)is
e en o odd, espec i ely.
(d)I each Gi,i= 1,2,...,n, is isomo phic o i s con e se, hen Halso is.
P oo . We only p o e he p ope ies (b) and (d) because he o he s can be p o ed
simila ly as hose o he Manha an s ee ne wo k in [4].
(b) The homomo phism om H o Q∗
nis
(u1, u2,...,un)→(π(u1), π(u2),...,π(un)),
which ans o m each e ex o Hin a bina y n-s ing o as i s image e ex in Q∗
n.
(d) As he Manha an p oduc is associa i e, we only need o deal wi h he case H=
G1k≡ G2. Since, Gi∼
=Giby hypo hesis, he e exis isomo phisms ψi, such ha
3
Γ±
Gi(ψi(ui)) = ψi(Γ∓
Gi(ui)), o all ui∈Vi. As ψiis a mapping be ween s able se s,
he pa i y πin Gican be de ined in such a way ha π(ui) is e en i and only i
π(ψi(ui)) is also e en. Then, he mapping Ψ de ined in Has
Ψ(u1, u2) := (ψ1(u1), ψ2(u2))
is he au omo phism om H o i s con e se H. Indeed, assuming ha , o ins ance,
π(u1), π(u2) a e e en, we ha e
ΨΓ+
H(u1, u2)= ΨΓ+
G1(u1), u2∪Ψu1,Γ+
G2(u2)
=ψ1(Γ+
G1(u1)), ψ2(u2)∪ψ1(u1), ψ2(Γ+
G2(u2))
=Γ−
G1(ψ1(u1)), ψ2(u2)∪ψ1(u1),Γ−
G2(ψ2(u2))
= Γ−
Hψ1(u1), ψ2(u2)
= Γ−
HΨ(u1, u2).
The o he cases, which co espond o o he pa i ies o π(u1) and π(u2), can be
p o ed simila ly.

As an example o a Manha an p oduc sa is ying he p ope y 3.1(e), see again Fig. 1.
4 The Manha an p oduc and he Manha an s ee ne -
wo ks
In his sec ion we show he ela ionship be ween he dig aphs ob ained by he Manha an
p oduc and he Manha an s ee ne wo ks.
P oposi ion 4.1. The Manha an p oduc o di ec ed cycles wi h an e en o de Niis a
Manha an s ee ne wo k. Mo e p ecisely, i Gi=CNi, hen
CN1k≡CN2k≡· · · k≡CNn=M(N1, N2,...,Nn).
P oo . Each cycle CNihas se o e ices Vi=ZNi, and adjacencies Γ+(ui) =
{ui+ 1 (mod Ni)}and Γ−(ui) = {ui−1 (mod Ni)}, such ha Vi0and Vi1a e he se s o
e en and odd e ices, espec i ely. Thus, he se o e ices in he Manha an p oduc
o di ec ed cycles is ZN1×ZN2×···×ZNnand each e ex (u1,...,ui,...,un) is adjacen
o he e ices (u1,..., i,...,un), 1 ≤i≤n, when
• i=ui+ 1 i Pj6=iπ(uj) is e en and, hence, Pj6=iujis also e en,
• i=ui−1 i Pj6=iπ(uj) is odd and, hence, Pj6=iujis also odd,
which co esponds o he de ini ion o he Manha an s ee ne wo k. 
Ano he expec ed esul o he Manha an p oduc is he ollowing:
P oposi ion 4.2. The Manha an p oduc o wo Manha an s ee ne wo ks is a Manha -
an ne wo k. Mo e p ecisely, i M1=M(N1
1, N1
2,...,N1
n1)and M2=M(N2
1, N2
2,...,N2
n2),
hen
M1k≡M2=M,
whe e M=M(N1
1,...,N1
n1, N2
1,...,N2
n2).
4
P oo . Bo h M1and M2a e bipa i e dig aphs wi h e ex se s Vα=ZNα
1×ZNα
2×
· · · × ZNα
nα,α= 1,2; whe eas M1k≡ M2has e ex se V=V1×V2. Le V(M) be he
e ex se o M. Then, we claim ha he na u al mapping Ψ : V→V(M), de ined
by Ψ(u1,u2) = (u1
1,...,u1
n1, u2
1,...,u2
n2) is an isomo phism be ween he co esponding
dig aphs. In p o ing his, le Vα
0and Vα
1be he s able se s o Mαcons i u ed, espec i ely,
by he e ices uα= (uα
1,...,uα
nα) whose sum o componen s Pnα
k=1 uα
kis e en o odd.
Wi h his con en ion, each e ex (u1,u2) o he Manha an p oduc M1k≡M2is adjacen
o he e ices ( 1,u2) and (u1, 2) whe e, o he i s ones,
• 1∈Γ+(u1) (in M1) i π(u2), and hence Pn2
k=1 u2
k, is e en;
• 1∈Γ−(u1) (in M1) i π(u2), and hence Pn2
k=1 u2
k, is odd.
In he i s case,
( 1,u2)Ψ
−→ (u1
1,...,u1
i+ (−1)
P
j6=iu1
j,...,u1
n1, u2
1,...,u2
n2)
= (u1
1,...,u1
i+ (−1)
P
j6=iu1
j+
P
n2
k=1 u2
k,...,u1
n1, u2
1,...,u2
n2) (1 ≤i≤n1).
Analogously, in he second case,
( 1,u2)Ψ
−→ (u1
1,...,u1
i−(−1)
P
j6=iu1
j,...,u1
n1, u2
1,...,u2
n2)
= (u1
1,...,u1
i+ (−1)
P
j6=iu1
j+
P
n2
k=1 u2
k,...,u1
n1, u2
1,...,u2
n2) (1 ≤i≤n1).
Al oge he , we ob ain he e ices adjacen o Ψ(u1,u2) = (u1
1,...,u1
n1, u2
1,...,u2
n2) in
M( h ough all he i-a cs, 1 ≤i≤n1). The adjacencies h ough he o he i-a cs,
n1+ 1 ≤i≤n1+n2come om he e ices (u1, 2). 
The esul o he abo e p oposi ion can be seen as a co olla y o he p oposi ion 4.1
and he associa i e p ope y. Indeed,
M1k≡M2=M(N1
1, N1
2,...,N1
n1)k≡M(N2
1, N2
2,...,N2
n2)
= (C1
N1k≡C1
N2k≡· · · k≡C1
Nn1)k≡(C2
N1k≡C2
N2k≡· · · k≡C2
Nn2)
=C1
N1k≡C1
N2k≡· · · k≡C1
Nn1k≡C2
N1k≡C2
N2k≡· · · k≡C2
Nn2
=M(N1
1, N1
2,...,N1
n1, N2
1, N2
2,...,N2
n2) = M.
5 Symme ies
In his sec ion we s udy he symme ies o he dig aphs ob ained by he Manha an
p oduc .
P oposi ion 5.1. Le Gibe e ex-symme ic dig aphs such ha hey a e isomo phic o
hei con e ses, i= 1,2,...,n. Then, he Manha an p oduc H=G1k≡ G2k≡ · · · k≡ Gnis
e ex-symme ic.
P oo . As be o e, le Gi= (Vi, Ai) be dig aphs wi h Vi=Vi0∪Vi1,i= 1,2,...,n.
Fi s , we show ha he e exis s an au omo phism Φ in H, which ans o ms a e -
ex (u1, u2,...,un) in o a e ex ( 1, 2,..., n), such ha ui, i∈Viji, o each i∈
{1,2, . . . , n}and some ji∈ {0,1}( ha is, bo h componen s ui, ia e in he same s able
se ). By hypo hesis, he e exis au omo phisms φiin Gi, Γ+
Gi(φi(wi)) = φi(Γ+
Gi(wi)), o
e e y wi∈Vi, such ha φi(ui) = i. Then, we de ine
Φ(w1, w2,...,wn) := (φ1(w1), φ2(w2),...,φn(wn)).
5

Then, assuming ha Pj6=iπ(wj) is e en and, hence, Pj6=iπ(φj(wj)) is also e en, we ha e
ΦΓ+
H(w1,...,wi,...,wn)= Φw1,...,Γ+
Gi(wi),...,wn
=φ1(w1),...,φi(Γ+
Gi(wi)),...,φn(wn)
=φ1(w1),...,Γ+
Gi(φi(wi)),...,φn(wn)
= Γ+
Hφ1(w1),...,φi(wi),...,φn(wn)
= Γ+
HΦ(w1,...,wi,...,wn),
which p o es ha Φ is an au omo phism. The p oo is simila o Pj6=iπ(wj) odd, by
using Γ−
Gi(φi(wi)) = φi(Γ−
Gi(wi)).
Mo eo e , we need an au omo phism Ψ, which ans o ms a e ex (u1,...,ui,...,un)
in o a e ex ( 1,..., i,..., n), such ha , o k6=i,uk, k∈Vkjkas be o e, while ui
and ibelong o di e en s able se s, o example, ui∈Vi0and i∈Vi1. In his case, he
au omo phism Ψ is buil up in he ollowing way. As each Giis isomo phic o i s con e se,
he e exis au omo phisms ψk, wi h k6=i, om Gk o Gk, Γ+
Gk(ψk(wk)) = ψk(Γ−
Gk(wk)),
o e e y wk∈Vk, such ha ψk(uk) = k; and ψi=φi(as in he i s case). Then, we
de ine Ψ as
Ψ(w1,...,wi,...,wn) := (ψ1(w1),...,ψi(wi),...,ψn(wn)).
Le us now assume ha k= 1 6=iand ha Pj6=1 π(wj) is e en, so ha , π(φi(wi)) +
Pj6=1,i π(ψj(wj)) is odd. Then, we ha e
ΨΓ+
H(w1,...,wi,...,wn)= ΨΓ+
G1(w1),...,wi,...,wn
=ψ1(Γ+
G1(w1)),...,φi(wi),...,ψn(wn)
=Γ−
G1(ψ1(w1)),...,φi(wi),...,ψn(wn)
= Γ+
Hψ1(w1),...,φi(wi),...,ψn(wn)
= Γ+
HΨ(w1,...,wi,...,wn).
Thus, Ψ is an au omo phism. Fo he case Pj6=1 π(wj) odd, he p oo is simila , using
Γ−
Gk(ψk(wk)) = ψk(Γ+
Gk(wk)). On he o he hand, he case k=iis p o ed as be o e, be-
cause assuming ha Pj6=iπ(wj) is e en, hen Pj6=iπ(ψj(wj)) is also e en. This comple es
he p oo . 
6 Cayley dig aphs and he Manha an p oduc
In his sec ion we in es iga e when he Manha an p oduc o Cayley dig aphs o is
again a Cayley dig aph. This gene alizes he case s udied in [4, 5] o Manha an s ee
ne wo ks, whe e he ac o s o he p oduc a e di ec ed cycles (see P op. 4.1), ha is,
Cayley dig aph o he cyclic g oups. Because o he associa i e p ope y o such p oduc
(see P op. 3.1(a)), we only need o s udy he case o wo ac o s.
Theo em 6.1. Le G1= Cay(Γ1,∆1)be a bipa i e Cayley dig aph o he g oup Γ1wi h
gene a ing se ∆1={a1,...,ap}and se o gene a ing ela ions R1, such ha he e exis s
a g oup au omo phism ψ1sa is ying ψ1(ai) = a−1
i, o i= 1,...,p. Le G2= Cay(Γ2,∆2)
be he bipa i e Cayley dig aph o he g oup Γ2wi h gene a ing se ∆2={b1,...,bq}and
se o gene a ing ela ions R2, such ha he e exis s a g oup au omo phism ψ2sa is ying
ψ2(bj) = b−1
j, o j= 1,...,q. Then, he Manha an p oduc H=G1k≡G2is he Cayley
dig aph o he g oup
Γ = hα1,...,αp, β1,...,βq|R′1, R′2,(αiβj)2= (αiβ−1
j)2= 1i, i 6=j, (2)
6
whe e R′1is he same se o gene a ing ela ions as R1changing aiby αi(and simila ly
o R′2).
P oo . Since o e e y u1∈Γ1and i= 1,...,p
ψ1(u1ai) = ψ(u1)ψ(ai) = ψ(u1)a−1
i,
hen ψ1is an (in olu i e) isomo phism o G1 o G1p ese ing colo s. The same holds
o ψ2and G2. Mo eo e , since G1, G2a e e ex-symme ic, P oposi ion 5.1 applies and
His also e ex-symme ic.
In ac , we will see ha i s au omo phism g oup con ains a egula subg oup. Wi h
his aim, no e i s ha , by using he abo e au omo phisms, we ha e he ollowing na u al
way o de ining he adjacencies o H(wi h “colo s” deno ed by αi, 1 ≤i≤p, and βj,
1≤j≤q):
(u1, u2)αi-a c
−→ (u1, u2)∗αi=u1ψπ(u2)
1(ai), u2,
(u1, u2)βj-a c
−→ (u1, u2)∗βj=u1, u2ψπ(u1)
2(bj).
Le us now p o e ha he mappings φ1i, φ2j, o 1 ≤i≤pand 1 ≤j≤q, de ined by
φ1i(u1, u2) = (aiu1, ψ2(u2)),
φ2j(u1, u2) = (ψ1(u1), bju2),
a e all colo -p ese ing isomo phisms o H. Indeed, o all 1 ≤i, j ≤pwe ha e
φ1i(u1, u2)∗αj=φ1iu1ψπ(u2)
1(aj), u2
=aiu1ψπ(u2)
1(aj), ψ2(u2)
=aiu1ψπ(ψ2(u2))
1(aj), ψ2(u2)
=aiu1, ψ2(u2)∗αj
=φ1i(u1, u2)∗αj,
whe e we ha e used ha π(u2) = π(ψ2(u2)) because u2can be exp essed as he p oduc
o he gene a o s bjand π(bj) = π(ψ2(bj)) = π(b−1
j) o all 1 ≤j≤q. Mo eo e , o all
1≤i≤p, 1≤j≤q, we also ha e
φ1i(u1, u2)∗βj=φ1iu1, u2ψπ(u1)
2(bj)
=aiu1, ψ2(u2)ψπ(u1)+1
2(bj)
=aiu1, ψ2(u2)ψπ(aj·u1)
2(bj)
=aiu1, ψ2(u2)∗βj
=φ1i(u1, u2)∗βj,
Simila ly, we ob ain
φ2i(u1, u2)∗αj=φ2i(u1, u2)∗αj,1≤i≤q, 1≤j≤p
φ2i(u1, u2)∗βj=φ2i(u1, u2)∗βj,1≤i, j ≤q.
To see ha he pe mu a ion g oup Γ = hφ1i, φ2j|1≤i≤p, 1≤j≤qiac s ansi i ely
on Γ1×Γ2, ha is, he e ex se o H, i is enough o show ha any e ex (u1, u2) can
be mapped in o e ex (e1, e2) (whe e e1and e2s and o he iden i y elemen s o Γ1and
Γ2, espec i ely) since, as i was men ioned abo e, His e ex-symme ic.
7
To his end, as ∆1is a gene a ing se , u−1
1can be exp essed in he o m, say, u−1
1=
ai1ai2···ai . Then,
φ1i1φ1i2···φ1i (u1, u2) = ai1ai2···ai , ψ
2(u2)
=e1, ψ
2(u2)
= (e1, 2),
whe e 2=u(−1)
2is ei he u2o u−1
2acco ding o he pa i y o . In any case, as ∆2is
also a gene a ing se , he in e se o his elemen can be w i en as, say, −1
2=bj1bj2···bjs.
Then,
φ2j1φ2j2···φ2js(e1, 2) = ψs
1(e1), e2
= (e1, e2),
as claimed.
Thus, he g oup Γ is a egula subg oup o he au omo phism g oup o Hand he
Manha an p oduc is a Cayley dig aph o Γ wi h gene a o s αi≡φ1iand βj≡φ2j.
Rega ding he s uc u e o Γ, le us check only one o he de ining ela ions in (2), as he
o he s can be p o ed simila ly.
(φ1iφ2j)2(u1, u2) = φ1iφ2jφi1φ2j(u1, u2)
=φ1iφ2jφ1iψ1(u1), bju2
=φ1iφ2jaiψ1(u1), b−1
jψ2(u2)
=φ1ia−1
iψ2
1(u1), ψ2(u2)
=ψ2
1(u1), ψ2
2(u2)
= (u1, u2).

This esul can be compa ed wi h he well-known ollowing one [11]: I G1and G2a e,
espec i ely, Cayley dig aphs o he g oups Γ1=ha1,...,ap|R1iand Γ2=hb1,...,bq|R2i,
hen i s di ec p oduc G1G2is he Cayley dig aph o he g oup
Γ = Γ1×Γ2=hα1,...,αp, β1,...,βq|R′
1, R′
2, αiβj=βjαii.
As an example o di ec p oduc o Cayley dig aphs, see Fig. 2, o be compa ed wi h
Fig. 1.
7 An al e na i e de ini ion
When each o he ac o s Gio he Manha an p oduc has a pola i y, ha is, he e
exis s an in olu i e au omo phism om Gi o Gi, we can gi e he ollowing al e na i e
de ini ion.
P oposi ion 7.1. Le ψibe an in olu i e au omo phism om Gi o Gi, o i= 1,2,...,n.
Then, he Manha an p oduc H=G1k≡ G2k≡ ... k≡ Gnis he dig aph wi h e ex se
V(Mn) = ZN1×ZN2× · · · × ZNnand he ollowing adjacencies (i= 1,2,...,n):
(u1, u2,...,ui,...,un) (ψ1(u1), ψ2(u2),..., i,...,ψn(un)),
whe e i∈Γ+(ui).
8
(1,1)
(3,0)
01
2
34
5
0
1
(0,0) (1,0)
(2,0)
(4,0)
(5,0)
(0,1)
(2,1)
(3,1)
(4,1)
(5,1)
Figu e 2: The di ec p oduc Cay(Z6,{1,3})K∗
2(undi ec ed lines s and o pai s o a cs
in opposi e di ec ions).
P oo . Fo he sake o simplici y, we espec i ely w i e he adjacencies o he i s
de ini ion and he al e na i e one as (i= 1,2,...,n):
(u1,...,ui,...,un)→u1,...,Γ(−1)
P
j6=iπ(uj)(ui),...,un,(3)
(u1,...,ui,...,un) ψ1(u1),...,Γ+(ui),...,ψn(un),(4)
whe e Γ+1 ≡Γ+and Γ−1≡Γ−.
The isomo phism om he i s de ini ion o he al e na i e one is:
Φ(u1,...,ui,...,un) = ψ
P
j6=1 π(uj)
1(u1),...,ψ
P
j6=iπ(uj)
i(ui),...,ψ
P
j6=nπ(uj)
n(un).
Indeed, le us see ha his mapping p ese es he adjacencies. Fi s , by (3), we ha e
ΦΓ+(u1,...,ui,...,un)=
ψ
P
j6=1 π(uj)+1
1(u1),...,ψ
P
j6=1 π(uj)
iΓ(−1)
P
j6=iπ(uj)(ui),...,ψ
P
j6=1 π(uj)+1
n(u1).(5)
Whe eas, by (4), we ha e
Γ+Φ(u1,...,ui,...,un)=
ψ
P
j6=1 π(uj)+1
1(u1),...,Γ+ψ
P
j6=iπ(uj)
i(ui),...,ψ
P
j6=nπ(uj)+1
n(un).(6)
To check ha he i- h en y in (5) and (6) ep esen s he same se , we dis inguish wo
cases:
•I Pj6=iπ(uj) = αis an e en numbe , hen ψα
i=Id (as ψiis in olu i e) and
IdΓ+(ui)= Γ+Id(ui).
•I Pj6=iπ(uj) = βis an odd numbe , hen ψβ
i=ψiand ψiΓ−(ui)= Γ+ψi(ui)
(as ψiis an au omo phism om Gi o Gi) .

In he case o he Manha an s ee ne wo k Mn,Gi=Ci(P op. 4.1). Then, a
simple way o choosing he in olu i e au omo phisms is ψi(ui) = −uimod Ni(in ac ,
i is eadily checked ha any isomo phism om Ci o Ciis in olu i e). Tha gi es he
ollowing de ini ion o Mn[4, 5]: The Manha an s ee ne wo k Mn=Mn(M1,...,Mn)
is he dig aph wi h e ex se ZN1× · · · × ZNnand he adjacencies
(u1,...,ui,...,un) (−u1,...,ui+ 1,...,−un) (1 ≤i≤n).
9