環狀完全圖的傳遞數的上界

An Upper Bound of the Routing Number of Circular Complete Graphs

賴星學(Hsing-Hsueh Lai)

指導教授 ： 潘志實

淡江大學/理學院/中等學校教師在職進修數學教學碩士學位班/碩士(2016年)

https://doi.org/10.6846/TKU.2016.00920

摘要

所謂連通圖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^+.

並列關鍵字

routing number ； circular complete graph

參考文獻

[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.

[5] F. K. Chung, Spectral Graph Theory, AMS Publications, Providence, RI, 1997.