论文摘要
超立方体（Qn）和k-ary n-立方体（Qnk）是常见的网络拓扑结构.它们具有很多优良的性质,如递归结构,结构对称,网络寻路算法简单等特点.环和线性阵列是并行分布计算最基本的两个网络结构.有许多基于它们设计出的高效低成本的算法.因而给出网络各种长度的路和圈是人们感兴趣的.各种互联网络最中心问题之一是寻找点不交的路.由于高效率通信网,容错路由等方面的应用,寻找网络中点不交的路问题备受关注.大型系统在运行时难免会出现一些故障,因此研究超立方体和k-ary n立方体点不交路和测地圈嵌入时考虑容错性是具有重要的现实意义.在这篇论文中,我们的主要结果如下：（1）令F是Qn3（n≥2）的边集,|F|≤2n-4,令x1,x2,y1,y2是Qn3中任意4个顶点,则在Qn3-F中存在两条顶点不交的路P1和P2,使得V（P1）∪V（P2）=V（Qn3）,这里P1连接x1和y1,P2连接x2和y2.（2）当n≥3,令超立方体中的边故障集|F|≤n-3,设x1,x2,y1,y2是Qn中任意4个顶点,使得距离d（x1,y1）和距离d（x2,y2）都是奇数,则在Qn-F中存在两条点不交路P1和P2,使得V（P1）∪V（P2）=V（Qn）,这里P1连接x1和y1,P2连接x2和y2,而且故障边数的上界是紧的.（3）假设u=（u1,u2,…,un）和v=（v1,v2,…,vn）是Qnk（n≥2,k≥3）中任意2个顶点,令这里0≤di≤k/2,（i=1,…,n）,记d=d1+d2+…+dn≥1N=kn,对于每个偶数l适合2d+2≤l≤N,则Qnk中有过u和v长为l的圈C,且C上u和v的距离为d.并且当且仅当有i和j满足1≤i<j≤n,使得di≥1且dj≥1,或有di=k/2且dj=0,j≠i,1≤j≤n,则又有l=2d；当奇数k≥3,记r=max{di},对于每个整数l适合2d+k-2r≤l≤N,则Qnk有过u和v长为l的圈C,且C上u和v的距离为d.而且l的下界2d+k-2r是紧的.