所謂連通圖G的傳遞數rt(G)，是指能使頂點的每一個置換，在r步通過交換不相交的邊的兩端點被傳遞的最小整數r值。在這篇研究報告中，我們將證明環狀完全圖K_(p/q)的傳遞數rt(K_(p/q) )≤ 2q  ,對於所有的p≥3q，其中p,q為正整數。

The routing number rt(G) of a connected graph G is the  minimum integer r so that every permutation of vertices can be routed in r steps by swapping the ends of disjoint edges. In this paper, we study  and prove the routing number of circular complete graph K_(p/q) is 
rt(K_(p/q) )≤2q， "for all" p≥3q，p,q∈Z^+.

目錄
第一章 ： 簡介………………………………..………………………1
第二章 ： 預備知識…………………………………..………………3
第三章 ： 環狀完全圖………………………………………..………9
第四章 ： 環狀完全圖的傳遞數的上界…………………….………13
第五章 ： 結論………………………….…………………….………27
參考文獻 ………………………………………………………………29

圖目錄
圖 1-a、1-b   簡單圖、非簡單圖 ……………..………………..………………...3
圖 2         鄰域與度數 ……………………………………….………………..4
圖 3         子圖與生成子圖 ……………….………………………….…….…4
圖 4         導出子圖 ……………………………….…………………………..5
圖 5         路徑P_8 ……………………..……………….………………………5
圖 6         迴圈C_6……………………………………………………………….6
圖 7         完全圖K_7…………..………………………………………………...7
圖 8         完全二分圖K_4,4………..…………………………………………….7
圖 9         配對、最大配對與完美配對………………………………………..8
圖 10        環狀完全圖 K_(14/4)………..……..…………...…………...9

參考文獻

[1]   N. Alon, F. R. K. Chung, and R. L. Graham, Routing permutations on graphs 
via matchings,SIAM J. Discrete Math., 7 (1994), pp. 513–530.
[2]   M. Baumslag and F. Annexstein, A unified framework for off-line permutation routing in parallel networks, Math. Systems Theory, 24 (1991), pp. 233–251.
[3]   V. E. Benes, Mathmatical Theory of Connecting Networks, Academic Press, New York, 1965.
[4]   A. Broder, A. Frieze, and E. Upfal, Existence and construction of edge disjoint paths on expander graphs, in Proc. 24th ACM Sympos. on Theory of Comput., Victoria, British Columbia, Canada, May 1992, pp. 140-149.
[5]   F. K. Chung, Spectral Graph Theory, AMS Publications, Providence, RI, 1997.
[6]   D. E. Knuth, The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, MA, 1973,p. 241.
[7]   Wei-Tian Li, Linyuan Lu, and Yiting Yang , Routing Numbers Of Cycles, Complete Bipartite Graphs, And Hypercubes, ,SIAM J. Discrete Math. Vol.24(2010), No.4, pp. 1482–1494.
[8]   L. Valiant, A scheme for fast parallel communication, SIAM J. Comput., 
11 (1982), pp. 350–361.
[9]  X. Zhu, Circular perfect graphs, J. Graph Theory, 48 (2005), pp. 186–209.