The matrixstar and the transposition graphs are considered as star graph variants that have various merits in graph theory such as node symmetry, fault tolerance, recursive scalability, etc. This paper describes an onetoone mapping algorithm from a matrixstar graph to a transposition graph using adjacent properties in graph theory. The result show that a matrixstar graph
MS
_{2,n}
can be embedded in a transposition graph
T
_{2n}
with dilation
n
or less and average dilation 2 or less.
Ⅰ. Introduction
Interconnection network architectures include a mesh, hypercube, star graphs. They can be categorized into three classes depending on the number of nodes: a star graph with
n
! nodes, a mesh with
n
×
k
nodes, and a hypercube with 2
n
nodes
[1]
. Star variations include transposition
[2]
, pancake
[3]
, standard star
[4]
, matrixstar
[5]
, macrostar
[6]
, and bubblesort
[7]
graph. The overall performance and scalability of a multiplecomputer system are significantly influenced by the architecture of the interconnection network. Therefore, the need to further develop interconnection networks is continuously growing with the development of parallel processing computers
[8]
. Most research on interconnection networks has focused on evaluating the parameters for measuring the performance of networks, including degree, diameter, fault tolerance, embedding, broadcasting, symmetry, and scalability
[1
,
9]
. Among these, embedding describes whether a network algorithm developed in an arbitrary interconnection network
G
can be efficiently executed in another interconnection network
H
through mapping the processors and communication links of
G
onto those of
H
. The common evaluation measurements for embedding are dilation, congestion, and expansion
[1
,
3
,
8

11]
.
The
n
dimensional star graph,
S_{n}
, is an edge and nodesymmetric graph containing
n
! nodes (
n
1)
n
!/2 edges. The nodes are assigned labels each being a distinct permutation of the set of integers {1,2,... ,
n
}. Two nodes are joined with a link labeled i if and only if the label of one can be obtained from the label of the other by swapping the first digit (conventionally the left most) and the ith digit where 1 <
i
≤
n
.
S_{n}
has various good properties such as disjoint paths, fault tolerance, partitionability, and recursive structure.
Fig. 1
shows a fourdimensional star graph
S_{4}
.
스타 그래프 S_{4} Fig. 1 Star graph S_{4}
One of the important interconnection network measures is the network cost. The network cost of an interconnection network is defined as the product of the degree and diameter of the network. The matrixstar graph improves the network cost of the wellknown star graph as an interconnection network. The matrixstar graph represents nodes as a matrix form, rather than a vector form. And it defines edges as operations converting matrix. The matrixstar
MS_{2,n}
has the half degrees of a star graph
S_{2n}
with the same number of nodes and is an interconnection network with the properties of node symmetry, maximum fault tolerance, and recursive structure, which a star graph also has. In a network cost, a matrixstar graph
MS_{2,n}
and a star graph
S_{2n}
are each about 3.5
n
^{2}
and 6
n
^{2}
, which means that the former has a better value by a certain constant than the latter has. Also, in terms of the embedding, we know that a star graph
S_{2n}
and a bubble sort graph
B_{2n}
embedded into matrixstar graph
MS_{2,n}
with unit expansion and dilation 5, and a transposition graph
T_{2n}
into it with expansion 1 and dilation 7. Also, the average dilation of the star graph
S_{2n}
is smaller than 3 and the bubble sort graph
B_{2n}
is smaller than 4
[5
,
11]
.
This paper analyzes an embedding algorithm from a matrixstar graph
MS_{2,n}
to a transposition graph
T_{2n}
. The matrixstar graph is generally considered a Cayley graph, and our result show that a matrixstar graph
MS_{2,n}
can be embedded in a transposition graph
T_{2n}
with dilation
n
or less and average dilation 2 or less.
Ⅱ. Definition of MatrixStar and Transposition Graphs
An interconnection network can be represented as an undirected graph
G
= (
V, E
), where
V
(
G
) is a set of nodes and
E
(
G
) is a set of edges. Each node and edge of
G
is presented with a processor and a communication channel between two processors in the interconnection network, respectively. Here,
V
(
G
) = {0, 1, 2,
,
n
–1} and there exists an edge (
v, w
) between two processors
v
and
w
of
G
if and only if a communication channel between
v
and
w
exists
[1
,
5
,
8]
.
In a matrixstar graph
MS_{2,n}
[5]
, a node
v
is represented as a 2 ×
n
matrix
, which consists of 2
n
distinct symbols {1, 2, ..., 2
n
}. In
MS_{2,n}
, three different types of edges are defined in the following three cases:
(1) Edge
C_{i}
that connects node
v
to node
w
in which the (1, 1)th symbol of
v
is exchanged with the (1,
i
)th symbol of
v
:
(2) Edge
E
that connects node
v
to node
w
in which the first row vector of
v
is interchanged with second row vector of
v
:
(3) Edge
R
that connect node
v
to node
w
in which the (1, 1)th symbol of
v
is swapped with the (2,1)th symbol of
v
:
Following these definitions, we can see that
MS_{2,n}
has (2
n
)! nodes and is a regular graph of degree
n
+1 (
n
≥ 2) because it can generate a matrix with the number of permutations expressed by 2
n
distinct symbols. However, when n = 1,
MS
_{2,1}
has degree 1 and it is a
K
_{2}
graph consisting of two nodes because the conditions defined in Edge
E
(2) and Edge
R
(3) are the same.
Fig. 2
shows an example of
MS_{2,2}
, in which the nodes are represented by 2×2 matrices
[11]
. The terms
node
and
matrix
are interchangeably used in this paper because a node is expressed by a matrix. The diameter of
MS_{2,n}
is 3.5
n
+2 or less and the broadcasting time is
n
^{2}
+4
n
4
[5]
.
행렬스타 그래프 MS_{2,2} Fig. 2 Matrixstar graph MS_{2,2}
An
n
dimensional transposition graph
T_{n}
[2]
is composed of
n
! nodes and
n
(
n
1)
n
!/4 edges. The address of each node is represented as a permutation of
n
distinct symbols, and there exist an edge between two nodes
v
and
w
if and only if the corresponding permutation of the node
w
is obtained from that of
v
by exchanging the positions of any two arbitrary symbols from {1, 2, ..,
n
} in
v
.
A transposition graph
T_{n}
is defined by the following formulas, where there are
n
distinct symbols <
N
> = {1, 2, ..,
n
}, and a permutation of <
N
>,
P
=
p
_{1}
p
_{2}
...
p
_{n}
,
p
_{i}
∈ <
N
>.
The transposition graph
T_{n}
is a regular graph with
n
(
n
1)/2 degree. It is also a node symmetry and bipartite graph. It has maximum fault tolerance because its diameter is
n
1, fault diameter is
n
, and node connectivity is equal to the number of its degree
n
(
n
1)/2
[2
,
8]
.
Fig. 3
shows a fourdimensional transposition graph
T_{4}
.
4차원 전위 그래프 T_{4} Fig. 3 4dimensional transposition graph T_{4}
Ⅲ. Embedding of Matrixstar Graph into Transposition Graph
Embedding entails mapping a specific graph
G
into another graph
H
to examine whether
G
is included in the graph
H
. Such embedding can be defined by a function
f
= (
ø
,
ρ
), where
ø
is a function for mapping the set of nodes
V
(
G
) in
G
onto the set of nodes
V
(
H
) in
H
, and
ρ
is a function for mapping an edge
e
= (
v, w
) in
G
to a path in
H
that links nodes
ø
(
v
) and
ø
(
w
). Evaluation parameters for embedding costs include dilation, congestion, and expansion. The dilation of an edge in
G
is the length of a path
ρ
(
e
) in
H
, the that of embedding
f
is the maximum value among all edge dilations in
G
. The congestion of an edge
e'
in
H
is the number of
ρ
(
e
) included in
e'
, and the congestion of embedding
f
is the maximum number among all edge congestions in
H
. The expansion of embedding
f
is the ratio of the number of nodes in
H
and
G
[1
,
8
,
11]
.
In this section, we analyze embedding between a matrixstar graph
MS
_{2,n}
and a transposition graph
T
_{2n}
. The analysis of embedding is accomplished by examining the dilation using node and adjacent properties between the two graphs
MS
_{2,n}
and
T
_{2n}
. The dilation of embedding is the number of edges required for the shortest path routing from
v'
to
u'
in
T
_{2n}
when mapping two adjacent nodes (
v
and
u
) of
MS
_{2,n}
onto two nodes (
v'
and
u'
) in
T
_{2n}
that have the identical addresses as the nodes
u
and
v
of
MS
_{2,n}
. Both in a matrixstar graph
MS
_{2,n}
and a transposition graph
T
_{2n}
, when a node
v
is adjacent to an arbitrary node
u
via an edge
k
, it is represented as
v
=
k
(
u
). If node
v
is reached from node
u
by sequentially applying an edge sequence <
k_{i}
,
k_{j}
,
k_{k}
>, it is denoted as
v
=
k_{k}
(
k_{j}
(
k_{i}
(
u
))). The onetoone mapping for two adjacent nodes of
MS
_{2,n}
onto the nodes of
T
_{2n}
is accomplished by converting the 1×2
n
matrix node format of
T
_{2n}
into the 2×
n
matrix node format of
MS
_{2,n}
. For example, when mapping two adjacent nodes
X
and
X'
of
MS
_{2,n}
onto the nodes of
T
_{2n}
, we convert the permutation of node
to
X
= (
x
_{1}
x
_{2}
...
x_{i}
...
x_{n}
x
_{n+1}
x
_{n+2}
...
x
_{n+i}
...
x
_{2n}
) by attaching the second row vector of
X
to its first row vector;
X'
is converted in the same way. Then we replace the symbol
t
, which consists of a node
T
=(
t
_{1}
t
_{2}
...
t_{i}
..
.t_{n}
t
_{n+1}
t
_{n+2}
...
t
_{n+i}
...
t
_{2n}
) of
T
_{2n}
with the symbol
x
, and map the node
X
of
MS
_{2,n}
to a node of
T
_{2n}
that is identical to the permutation of node
X
.
Theorem 1.
A matrixstar graph
MS
_{2,n}
can be embedded into a transposition graph
T
_{2n}
with dilation
n
or less.
Proof.
We analyze this embedding by dividing into three cases based on three different types of edges defined in a matrixstar graph
MS
_{2,n}
: Edge
C_{i}
,
E
, and
R
.
Let node
X
be
(i.e.,
x
_{1}
x
_{2}
x
_{3}
...
x
_{i}
...
x
_{n}
x
_{n+1}
x
_{n+2}
...
x
_{n+i}
...
x
_{2n}
) and an adjacent node of
X
be
X'
.
Case 1.
Edge
C_{i}
, 2 ≤
i
≤
n
In
MS
_{2,n}
, an adjacent node
X'
to node
via edge
C_{i}
is
. If we convert it into the 1×2
n
matrix node format of
T
_{2n}
,
X'
= (
x_{i}x_{2}x_{3}
...
x
_{1}
.. .
x
_{n}
x
_{n+1}
x
_{n+2}
...
x
_{n+i}
...
x
_{2n}
). When mapping nodes
X
and
X'
in
MS
_{2,n}
onto nodes
T
(=
t
_{1}
t
_{2}
t
_{3}
...
t_{i}
...
t_{n}
t
_{n+1}
t
_{n+2}
...
t
_{n+i}
...
t
_{2n}
) and
T'
(=
t_{i}
t
_{2}
t
_{3}
...
t
_{1}
...
t_{n}
t
_{n+1}
t
_{n+2}
...
t
_{n+i}
...
t
_{2n}
) in
T
_{2n}
, this embedding is possible with dilation 1 because nodes
T
and
T'
are adjacent to each other via edge
T
(1,
i
) in
T
_{2n}
.
Case 2.
Edge
R
In
MS
_{2,n}
, an adjacent node
X'
to node
via edge
R
is
and
X'
= (
x
_{n+1}
x
_{2}
x
_{3}
...
x_{i}
...
x_{n}
x
_{1}
x
_{n+2}
...
x
_{n+i}
...
x
_{2n}
) if we convert it into the 1×2
n
matrix node format of
T
_{2n}
. When mapping nodes
X
and
X'
in
MS
_{2,n}
onto nodes
T
(=
t
_{1}
t
_{2}
t
_{3}
...
t_{i}
...
t_{n}
t
_{n+1}
t
_{n+2}
...
t
_{n+i}
...
t
_{2n}
) and
T'
(=
t
_{n+1}
t
_{2}
t
_{3}
...
t_{i}
...
t_{n}
t
_{1}
t
_{n+2}
...
t
_{n+i}
...
t
_{2n}
)in
T
_{2n}
, this embedding is possible with dilation 1 because nodes
T
and
T'
are adjacent to each other via edge
T
(1,
n
+1) in
T
_{2n}
.
Case 3.
Edge
E
In
MS
_{2,n}
, an adjacent node
X'
to node
via edge
E
is
, and if we convert it into the 1×2
n
matrix node format of
T
_{2n}
,
X'
= (
x
_{n+1}
x
_{n+2}
...
x
_{n+i}
...
x
_{2n}
x
_{1}
x
_{2}
...
x_{i}
...
x_{n}
), when mapping nodes
X
and
X'
in
MS
_{2,n}
onto nodes
T
(=
t
_{1}
t
_{2}
t
_{3}
...
t_{i}
...
t
_{n}
t
_{n+1}
t
_{n+2}
...
t
_{n+i}
...
t
_{2n}
) and
T'
(=
t
_{n+1}
t
_{n+2}
...
t
_{n+i}
...
t
_{2n}
t
_{1}
t
_{2}
...
t_{i}
...
t_{n}
) in
T
_{2n}
, we can see that the nodes
T
and
T'
in
T
_{2n}
are not adjacent to each other by the edge definition of the transposition graph
T
_{2n}
. Thus, we analyze the dilation of this embedding using the number of edges used for the shortest path routing from node
T
to node
T'
in
T
_{2n}
. The edge sequence required for routing from node
T
(=
t
_{1}
t
_{2}
t
_{3}
...
t_{i}
...
t_{n}
t
_{n+1}
t
_{n+2}
...
t
_{n+i}
...
t
_{2n}
) to node
T'
(=
t
_{n+1}
t
_{n+2}
...
t
_{n+i}
...
t
_{2n}
t
_{1}
t
_{2}
...
t_{i}
...
t_{n}
) is <
T
(1,
n
+1),
T
(2,
n
+2),
T
(3,
n
+3), ...,
T
(
i
,
n
+
i
), ...,
T
(
n
, 2
n
) >; that is, we swap the first symbol
t
_{1}
with the (
n
+1)th symbol
t
_{n+1}
of
T
, and exchange the second symbol
t
_{2}
with the (
n
+2)th symbol
t
_{n+2}
; next, we swap the third symbol
t
_{3}
with the (
n
+3)th symbol
t
_{n+3}
, and repeat this exchanging process until the nth symbol tn is interchanged with the (2
n
)th symbol
t
_{2n}
of
T
. Thus, the number of edges required for the routing from node
T
and node
T'
in
T
_{2n}
is
n
, when mapping nodes
X
and
X'
in
MS
_{2,n}
onto nodes
T
(=
t
_{1}
t
_{2}
t
_{3}
...
t
_{i}
...
t_{n}
t
_{n+1}
t
_{n+2}
...
t
_{n+i}
...
t
_{2n}
) and
T'
(=
t
_{n+1}
t
_{n+2}
...
t
_{n+i}
...
t
_{2n}
t
_{1}
t
_{2}
...
t_{i}
...
t_{n}
) in
T
_{2n}
. Consequently, this embedding is possible with dilation
n
.
Corollary 2.
A matrixstar graph
MS
_{2,n}
can be embedded into a transposition graph
T
_{2n}
with average dilation of 2 or less.
Proof.
In
MS
_{2,n}
, three different types of edges are existed: (
C_{i}
,
R
,
E
). The number of nodes adjacent to an arbitrary node
via edge
C_{i}
is
n
1, and the number of nodes adjacent to node
X
via edge
E
or edge
R
is 1. Therefore, we can obtain an average dilation by dividing the sum of the total dilation of the all nodes in
MS
_{2,n}
by the total number of edges. Because the necessary dilation to map node
X
from all nodes of graph
MS
_{2,n}
via edge
C_{i}
or edge
R
is 1, and the necessary dilation to map node
X
from all nodes of
MS
_{2,n}
via edge
E
is
n
, the sum of the total dilation can be expressed as follows: {((2
n
)! ´ (
n
 1)) / 2} + {(2
n
)! / 2} + {((2
n
)! ´
n
) / 2} = ((2
n
)! ´ 2
n
) / 2. Therefore, the average dilation is approximately 2 or less, because it results from the division of the total dilation by the total number of edges and is equal to (((2
n
)! ´ 2
n
) / 2) / ((2
n
)! ´ (
n
+ 1)) / 2 = 2
n
/ (
n
+ 1).
Ⅳ. Conclusion
In this paper, we have described a onetoone mapping method between a matrixstar graph and a transposition graph using adjacent properties in graph theory, and analyzed the dilation that results from this mapping. Our result indicated that a matrixstar graph
MS
_{2,n}
can be embedded in a transposition graph
T
_{2n}
with dilation n or less and average dilation 2 or less. The results mean that various algorithms designed for
MS
_{2,n}
can be executed on
T
_{2n}
efficiently. And the results reported here are expected to be extremely useful for analysis of embeddings among
MS
_{2,n}
and other star graph variants.
BIO
김종석(JongSeok Kim) 컴퓨터과학과 이학박사 ※관심분야 : 상호연결망, 그래프 이론, 계산 이론
이형옥(HyeongOk Lee) 컴퓨터과학과 이학박사 ※관심분야 : 상호연결망, 그래프 이론, 계산 이론
Kim M.
,
Kim D.W.
,
Lee H.O.
2010
“Embedding Algorithms for Star, BubbleSort, RotatorFaberMoore, and Pancake Graphs,”
Proceedings of the 10th international conference on Algorithms and Architectures for Parallel Processing
348 
357
Latifi S.
,
Srimani P. K.
1996
“Transposition Networks as a Class of FaultTolerant Robust Networks,”
IEEE Trans. Computers
http://dx.doi.org/10.1109/12.485375
45
(2)
230 
238
DOI : 10.1109/12.485375
Ranka S.
,
Wang J.
,
Yeh N.
1993
“Embedding Meshes on the Star Graph,”
Journal of Parallel and Distributed Computing
http://dx.doi.org/10.1006/jpdc.1993.1098
19
131 
135
DOI : 10.1006/jpdc.1993.1098
Akers S. B.
,
Harel D.
,
Krishnamurthy B.
1987
“The Star Graph: An Attractive Alternative to the nCube,”
Proceedings of the International Conference on Parallel Processing
393 
400
Lee H.O.
,
Kim J.S.
,
Park K.W.
,
Seo J.H.
,
Oh E.
2005
“MatrixStar Graphs: A New Interconnection Network Based on Matrix Operations,”
Proceedings of the International Conference on AsiaPacific Computer Systems Architecture
478 
487
Yeh C. H.
,
Varvarigos E. A.
1998
“MacroStar Networks: Efficient LowDegree Alternatives to Star Graphs,”
IEEE Trans. Parallel and Distributed Systems
http://dx.doi.org/10.1109/71.730528
9
(10)
987 
1003
DOI : 10.1109/71.730528
Chou Z. T.
,
Hsu C. C.
,
Sheu J. P.
1996
“Bubblesort Star graphs: A New Interconnection Network,”
Proceedings of the 9th International conference on Parallel and Distributed Systems
41 
48
Lee H.O.
,
Sim H.
,
Seo J.H.
,
Kim M.
2010
“Embedding Algorithms for BubbleSort, MacroStar, and Transposition Graphs,”
Proceedings of the 2010 IFIP international conference on Network and parallel computing
134 
143
Wu A. Y.
1985
“Embedding of Tree Networks into Hypercubes,”
Journal of Parallel and Distributed Computing
http://dx.doi.org/10.1016/07437315(85)900267
2
238 
249
DOI : 10.1016/07437315(85)900267
Deng W.
,
Luo Q.
2012
“Embedding Complete Binary Trees into Locally Twisted Cubes,”
Advanced Engineering Forum
http://dx.doi.org/10.4028/www.scientific.net/AEF.67.70
67
70 
75
DOI : 10.4028/www.scientific.net/AEF.67.70
Kim J.S.
,
Kim M.
,
Sim H.
,
Lee H.O.
2011
“Embedding Algorithms for BubbleSort, Pancake, and MatrixStar Graphs,”
Communications in Computer and Information Science
http://dx.doi.org/10.1007/9783642209758_27
150
243 
252
DOI : 10.1007/9783642209758_27