超立方體中互相獨立線性配置之嵌入研究

Abstract

在訊息傳遞中, 在每個接收點是要避免碰撞的事件發生, 因此訊息傳送路徑中互相獨立的特性是相當重要的. 我們說兩條相同長度的路徑是獨立的, 就代表著除了起始點與終點之外, 其餘的時間點中, 在同一個時間所經過的目標是不會相同的; 在這篇論文中, 我們探討研究了在 n 維超立方體中, 任意的兩點中可以存在著(n-1)條任意長度之互相獨立的路徑, 其長度由兩點間最短(漢明距離)到最長(漢米爾頓距離)都有.

We say that two paths P0= <u0,u1,...uk-1> and P1= <v0,v1,...,vk-1> are independent if u0=v0, l(P0)=l(P1) and P0(i)!=P1(i) fro every 1<i<k-1. The set of paths {P0,P1,...,Ps} of G are mutually independent if any two different paths in the set are independent. In this paper, we prove that there exist (n-1) mutually independent paths of length l joining any vertices u and v such that h(u,v)+2 <= l <= 2^n-1 and n>=4.