An Algorithm for OnetoOne Mapping Matrixstar Graph into Transposition Graph
행렬스타 그래프를 전위 그래프에 일대일 사상하는 알고리즘
 Publish: Journal of the Korea Institute of Information and Communication Engineering Volume 18, Issue5, p1110~1115, 31 May 2014

ABSTRACT
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 graphT _{2n} with dilationn or less and average dilation 2 or less.
행렬스타 그래프와 전위 그래프는 스타 그래프 부류로 그래프 이론 관점에서 노드 대칭성, 고장 허용도, 재귀적 확장성 등 스타그래프의 장점을 가지고 있는 상호연결망이다. 본 논문에서는 그래프 이론의 인접 성질을 이용하여 행렬스타 그래프와 전위 그래프 사이의 일대일 사상 알고리즘을 제안한다. 행렬스타 그래프가 전위 그래프에 연장율 n 이하에 사상할 수 있음을 보이며, 평균 연장율이 2 이하임을 보인다.

KEYWORD
Algorithm , Interconnection network , Matrixstar graph , Onetoone mapping , Transposition graph

Ⅰ. 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 withn ×k nodes, and a hypercube with 2n 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 networkG can be efficiently executed in another interconnection networkH through mapping the processors and communication links ofG onto those ofH . The common evaluation measurements for embedding are dilation, congestion, and expansion [1,3,811].The
n dimensional star graph,S_{n} , is an edge and nodesymmetric graph containingn ! 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 graphS_{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 graphS_{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 graphMS_{2,n} and a star graphS_{2n} are each about 3.5n ^{2} and 6n ^{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 graphS_{2n} and a bubble sort graphB_{2n} embedded into matrixstar graphMS_{2,n} with unit expansion and dilation 5, and a transposition graphT_{2n} into it with expansion 1 and dilation 7. Also, the average dilation of the star graphS_{2n} is smaller than 3 and the bubble sort graphB_{2n} is smaller than 4 [5,11].This paper analyzes an embedding algorithm from a matrixstar graph
MS_{2,n} to a transposition graphT_{2n} . The matrixstar graph is generally considered a Cayley graph, and our result show that a matrixstar graphMS_{2,n} can be embedded in a transposition graphT_{2n} with dilationn 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 ), whereV (G ) is a set of nodes andE (G ) is a set of edges. Each node and edge ofG 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 processorsv andw ofG if and only if a communication channel betweenv andw exists [1,5,8].In a matrixstar graph
MS_{2,n} [5], a nodev is represented as a 2 ×n matrix , which consists of 2n distinct symbols {1, 2, ..., 2n }. InMS_{2,n} , three different types of edges are defined in the following three cases:(1) Edge
that connects nodeC _{i}v to nodew in which the (1, 1)th symbol ofv is exchanged with the (1,i )th symbol ofv :(2) Edge
that connects nodeE v to nodew in which the first row vector ofv is interchanged with second row vector ofv :(3) Edge
that connect nodeR v to nodew in which the (1, 1)th symbol ofv is swapped with the (2,1)th symbol ofv :Following these definitions, we can see that
MS_{2,n} has (2n )! nodes and is a regular graph of degreen +1 (n ≥ 2) because it can generate a matrix with the number of permutations expressed by 2n distinct symbols. However, when n = 1,MS _{2,1} has degree 1 and it is aK _{2} graph consisting of two nodes because the conditions defined in EdgeE (2) and EdgeR (3) are the same. Fig. 2 shows an example ofMS_{2,2} , in which the nodes are represented by 2×2 matrices [11]. The termsnode andmatrix are interchangeably used in this paper because a node is expressed by a matrix. The diameter ofMS_{2,n} is 3.5n +2 or less and the broadcasting time isn ^{2}+4n 4 [5].An
n dimensional transposition graphT_{n} [2] is composed ofn ! nodes andn (n 1)n !/4 edges. The address of each node is represented as a permutation ofn distinct symbols, and there exist an edge between two nodesv andw if and only if the corresponding permutation of the nodew is obtained from that ofv by exchanging the positions of any two arbitrary symbols from {1, 2, ..,n } inv .A transposition graph
T_{n} is defined by the following formulas, where there aren 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 withn (n 1)/2 degree. It is also a node symmetry and bipartite graph. It has maximum fault tolerance because its diameter isn 1, fault diameter isn , and node connectivity is equal to the number of its degreen (n 1)/2 [2,8]. Fig. 3 shows a fourdimensional transposition graphT_{4} .Ⅲ. Embedding of Matrixstar Graph into Transposition Graph
Embedding entails mapping a specific graph
G into another graphH to examine whetherG is included in the graphH . Such embedding can be defined by a functionf = (ø ,ρ ), whereø is a function for mapping the set of nodesV (G ) inG onto the set of nodesV (H ) inH , andρ is a function for mapping an edgee = (v, w ) inG to a path inH that links nodesø (v ) andø (w ). Evaluation parameters for embedding costs include dilation, congestion, and expansion. The dilation of an edge inG is the length of a pathρ (e ) inH , the that of embeddingf is the maximum value among all edge dilations inG . The congestion of an edgee' inH is the number ofρ (e ) included ine' , and the congestion of embeddingf is the maximum number among all edge congestions inH . The expansion of embeddingf is the ratio of the number of nodes inH andG [1,8,11].In this section, we analyze embedding between a matrixstar graph
MS _{2,n} and a transposition graphT _{2n}. The analysis of embedding is accomplished by examining the dilation using node and adjacent properties between the two graphsMS _{2,n} andT _{2n}. The dilation of embedding is the number of edges required for the shortest path routing fromv' tou' inT _{2n} when mapping two adjacent nodes (v andu ) ofMS _{2,n} onto two nodes (v' andu' ) inT _{2n} that have the identical addresses as the nodesu andv ofMS _{2,n}. Both in a matrixstar graphMS _{2,n} and a transposition graphT _{2n}, when a nodev is adjacent to an arbitrary nodeu via an edgek , it is represented asv =k (u ). If nodev is reached from nodeu by sequentially applying an edge sequence <k_{i} ,k_{j} ,k_{k} >, it is denoted asv =k_{k} (k_{j} (k_{i} (u ))). The onetoone mapping for two adjacent nodes ofMS _{2,n} onto the nodes ofT _{2n} is accomplished by converting the 1×2n matrix node format ofT _{2n} into the 2×n matrix node format ofMS _{2,n}. For example, when mapping two adjacent nodesX andX' ofMS _{2,n} onto the nodes ofT _{2n}, we convert the permutation of node toX = (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 ofX to its first row vector;X' is converted in the same way. Then we replace the symbolt , which consists of a nodeT =(t _{1}t _{2}...t_{i} ...t_{n} t _{n+1}t _{n+2}...t _{n+i}...t _{2n}) ofT _{2n} with the symbolx , and map the nodeX ofMS _{2,n} to a node ofT _{2n} that is identical to the permutation of nodeX .Theorem 1. A matrixstar graphMS _{2,n} can be embedded into a transposition graphT _{2n} with dilationn or less.Proof. We analyze this embedding by dividing into three cases based on three different types of edges defined in a matrixstar graphMS _{2,n}: Edge ,C _{i} , andE .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 ofX beX' . EdgeCase 1. C_{i} , 2 ≤i ≤n In
MS _{2,n}, an adjacent nodeX' to node via edgeC_{i} is . If we convert it into the 1×2n matrix node format ofT _{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 nodesX andX' inMS _{2,n} onto nodesT (=t _{1}t _{2}t _{3}...t_{i} ...t_{n} t _{n+1}t _{n+2}...t _{n+i}...t _{2n}) andT' (=t_{i} t _{2}t _{3}...t _{1}...t_{n} t _{n+1}t _{n+2}...t _{n+i}...t _{2n}) inT _{2n}, this embedding is possible with dilation 1 because nodesT andT' are adjacent to each other via edgeT (1,i ) inT _{2n}. EdgeCase 2. R In
MS _{2,n}, an adjacent nodeX' to node via edgeR is andX' = (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×2n matrix node format ofT _{2n}. When mapping nodesX andX' inMS _{2,n} onto nodesT (=t _{1}t _{2}t _{3}...t_{i} ...t_{n} t _{n+1}t _{n+2}...t _{n+i}...t _{2n}) andT' (=t _{n+1}t _{2}t _{3}...t_{i} ...t_{n} t _{1}t _{n+2}...t _{n+i}...t _{2n})inT _{2n}, this embedding is possible with dilation 1 because nodesT andT' are adjacent to each other via edgeT (1,n +1) inT _{2n}. EdgeCase 3. E In
MS _{2,n}, an adjacent nodeX' to node via edgeE is , and if we convert it into the 1×2n matrix node format ofT _{2n},X' = (x _{n+1}x _{n+2}...x _{n+i}...x _{2n}x _{1}x _{2}...x_{i} ...x_{n} ), when mapping nodesX andX' inMS _{2,n} onto nodesT (=t _{1}t _{2}t _{3}...t_{i} ...t _{n}t _{n+1}t _{n+2}...t _{n+i}...t _{2n}) andT' (=t _{n+1}t _{n+2}...t _{n+i}...t _{2n}t _{1}t _{2}...t_{i} ...t_{n} ) inT _{2n}, we can see that the nodesT andT' inT _{2n} are not adjacent to each other by the edge definition of the transposition graphT _{2n}. Thus, we analyze the dilation of this embedding using the number of edges used for the shortest path routing from nodeT to nodeT' inT _{2n}. The edge sequence required for routing from nodeT (=t _{1}t _{2}t _{3}...t_{i} ...t_{n} t _{n+1}t _{n+2}...t _{n+i}...t _{2n}) to nodeT' (=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 , 2n ) >; that is, we swap the first symbolt _{1} with the (n +1)th symbolt _{n+1} ofT , and exchange the second symbolt _{2} with the (n +2)th symbolt _{n+2}; next, we swap the third symbolt _{3} with the (n +3)th symbolt _{n+3}, and repeat this exchanging process until the nth symbol tn is interchanged with the (2n )th symbolt _{2n} ofT . Thus, the number of edges required for the routing from nodeT and nodeT' inT _{2n} isn , when mapping nodesX andX' inMS _{2,n} onto nodesT (=t _{1}t _{2}t _{3}...t _{i}...t_{n} t _{n+1}t _{n+2}...t _{n+i}...t _{2n}) andT' (=t _{n+1}t _{n+2}...t _{n+i}...t _{2n}t _{1}t _{2}...t_{i} ...t_{n} ) inT _{2n}. Consequently, this embedding is possible with dilationn .Corollary 2. A matrixstar graphMS _{2,n} can be embedded into a transposition graphT _{2n} with average dilation of 2 or less.Proof. InMS _{2,n}, three different types of edges are existed: ( ,C _{i}R ,E ). The number of nodes adjacent to an arbitrary node via edgeC_{i} isn 1, and the number of nodes adjacent to nodeX via edgeE or edgeR is 1. Therefore, we can obtain an average dilation by dividing the sum of the total dilation of the all nodes inMS _{2,n} by the total number of edges. Because the necessary dilation to map nodeX from all nodes of graphMS _{2,n} via edgeC_{i} or edgeR is 1, and the necessary dilation to map nodeX from all nodes ofMS _{2,n} via edgeE isn , the sum of the total dilation can be expressed as follows: {((2n )! ´ (n  1)) / 2} + {(2n )! / 2} + {((2n )! ´n ) / 2} = ((2n )! ´ 2n ) / 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 (((2n )! ´ 2n ) / 2) / ((2n )! ´ (n + 1)) / 2 = 2n / (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 graphT _{2n} with dilation n or less and average dilation 2 or less. The results mean that various algorithms designed forMS _{2,n} can be executed onT _{2n} efficiently. And the results reported here are expected to be extremely useful for analysis of embeddings amongMS _{2,n} and other star graph variants.

[그림 1.] 스타 그래프 S4

[그림 2.] 행렬스타 그래프 MS2,2

[그림 3.] 4차원 전위 그래프 T4