### 投影片 1

```All-to-all broadcast problems on
Cartesian product graphs
Jen-Chun Lin

Outline
• Introduction
• Main result
 m n  1
1. t (Cm □Cn )  
for all m, n  3

 2 
 m(2n  1)  1
2. t (Cm □K 2 n1 )  
for all m, n, m  3, n  1

n 1


 4m n 2m  2n 
3. t ( K 2 m1□K 2 n1 )  
for all m, n, m  n  1

mn


 4 n  1
4. t (Q2 n )  
 for all n  Ν
 n 
• Reference
Introduction
Suppose each vertex has a private message
needed to send to every other vertices(all-to-all
broadcast). At each time unit, vertices exchange
their messages under the following constraints:
(1) only one message can travel a link at a time
unit
(2) a message requires one time unit to be
transferred between two nodes
(3) each vertex can use all of its links at the
same time
Chang et al.
They gave upper and lower bounds for all-toall broadcast number t G  (the shortest time
needed to complete the all-to-all broadcast) of
graphs and give formulas for the all-to-all
broadcast number of trees, complete bipartite
graphs and double loop networks under this
model.
of Cartesian product of
cycles and complete graphs
Given a graph G and a positive integer t, we
use G◦t to denote the multigraph obtained from
G by replacing each edge uv in E(G) with k
edges uv1, uv2 ,...,uvt .
AB2
AB
1
3
AB
3
1
②
③
2
BC1
①
1
①② ③
4
CD3
G 3
③
②
②① ③
3
①
CD
1
BC3
BC
2
CD
2
AB1
H A3
BC
DA
3
2
CD2
AB
AB
3
2
DA
BC1
CD
3
1
H B3
H
3
D
BC
3
DA2
H C3
CD1
For a graph G with V G  v0 , v1,...,vn1, a set of
t
t
t
H
,
H
,...,
H
edge-disjoint subgraphs v0 v1
vn1 of G◦t is
Theorem
 m n  1
t (Cm □Cn )  
for allm, n  3

 2 
The broadcasting tree H100,0 of C4 □C5 10 for a0,0.
①
②
③
0,0
2,0
3,0
1,0
①
②
0,1
③
1,1
2,1
④
3,1
④
0,2
⑤
⑤
1,2
⑥
0,3
1,3
⑧
0,4
⑥
⑦
2,2
3,2
⑦
2,3
⑧
3,3
⑨
⑨
1,4
2,4
⑩
3,4
0,0
0,1
1, 2  of
C4 □C5 10 for a1,2.
2,0
1,0
⑩
4,5
3,0
⑧
1,1
⑨
⑨
2,1
3,1
③
0,2
0,3
⑤
⑦
0,4
1,2
①
2,2
①
④
②
1,3
⑥
2,3
②
3,2
③
⑦
3,3
④
1,4
⑤
2,4
⑥
3,4
Lemma
Given a graph G, t G   t if and only if there
exists a t-broadcasting systm of G.
 m n  1
t (Cm □C n )  t  

 2 
Lemma
For any graph G with V G  n and EG  m ,
 n(n  1) 
t G   

 m 
 m nm n 1  m n 1
t (Cm □Cn )  




 2m n   2 
Theorem
 m n  1
t (Cm □Cn )  
for allm, n  3

 2 
Theorem
 m(2n  1)  1
t (Cm □K 2 n1 )  
for all m, n, m  3, n  1

n 1


The perfect broadcasting tree H70,0 of C5□K5  8 for a0,0.
②
①
③
④
0,0
2,0
3,0
4,0
1,0
①
0,1
①
③
1,1
2,1
1,2
⑤
3,2
2,2
0,3
②
0,4
⑤
⑦
1,3
1,4
⑥
⑧
2,3
4,2
⑧
3,3
4,3
⑧
⑦
2,4
4,1
⑥
⑦
②
⑥
3,1
⑤
④
③
0,2
④
3,4
4,4
Theorem
 4m n 2m  2n 
t ( K 2 m1□K 2 n1 )  
for allm, n, m  n  1

mn


For positive integers m and n with m  n  1.
We set
 m,n  2n, when m  2n

 m,n  m, when 2n  m  3n
  3n, when m  3n
 m,n
The subgraph H60,0 of K9 □K5  6.
1
0,0 1
1
1,0
1
2,0
3
2
1
4,0
3,0
3
2
3
2
6,0
5,0
3
2
4
7,0
5
8,0
6
0,1 3
1
0,2
4
4
4
5
5
5
6
6
6
4
2
0,3
5
2
0,4
6
3
4
5
6
0,0
1,0
2,0
3,0
4,0
6,0
5,0
7,0
8,0
0,1
7
0,2
7
7
7
0,3
7
0,4
7
8
8
of hypercubes
Theorem
 4 n  1
t (Q2 n )  
 for alln  1
 n 
0
Definition
Qn  P2 □ P2 □...□ P2
n個P2 
Q2 n  P2 □ P2 □...□ P2 □ P2 □...□ P2
3
2n個P2 
1
2
 C4 □C 4 □...□C 4
n個
let V( Q2 n )  a0 , a1 ,...,an 1  : ai  0,1,2,3 i,1  i  n
E(Q2 n )  a0 , a1 ,...,an 1 b0 , b1 ,...,bn 1  : bi  ai  14 and b j  a j j  i
For a vertex v  a0 , a1,...,an1  in V Q2n , the weight of v ,
n 1
denoted by wv  , is defined by wv    ai .
i 0
Definition
n
A
For the set  A  A      A, the right-shift of
n
n

A
elements in A is a function from to An defined
By  k a0 , a1,...,an1  = ak , ak 1,...,an1, a0 , a1,...,ak 1 
 a0 , a1,...,an1  An .  k, 0  k  n  1.
ex:  3 1,2,3,0,1 = 0,1,1,2,3
Definition
• the orbit of v, denoted by Ov .


Ov   k v : k  0,1,2,...,n 1
• A vertex v in V Q2n  is said to be
type1: if Ov  n

n
type2 : if Ov  n  Ov   2 
Definition
Let Α  v V Q2 n :v is type1, and
Let  v V Q2 n :v is type2
Theorem
 4 n  1
t (Q2 n )  
 for alln  Ν
 n 
(0,0,………,0)

wv   1
wv   2

………
(1,0,………,0) (0,1,………,0)
(2,0,………,0)
(1,0,………,1)
(0,2,………,0)
(0,0,………,1)
(0,0,………,2)
(1,1,………,0)
Lemma
For each vin Α with wv   2, there exists a
vertex u in A with uv  E Q2 n  and
wu   wv   1.
Lemma
If v  a0 , a1 ,...,an1  is in B, then i, 0  i  n  1,
ui  a0 , a1 ,...,ai  14 ,...,an1  is in A.
(0,1,………,1) 
A
(1,1,………,1)  B
0,0
1
0,1
7
2
1,1
0,2
0,3
tree H80,0  of Q4  8.
1,0
2
4
1
2,0
3
4
1,2
3
3,0
2,1
5
3,1
6
3,2
5
1,3
7
2,2
6
2,3
8
3,3