关于3连通图的容错直径和宽直径

容错直径和宽直径是度量网络可靠性和有效性的重要参数．对任意k连通图，它的容错直径Dk不超过宽直径dk,本证明：当D2=2时，d3≤max{D， l，2D3-2}；当D2≥3时，d3≤(D2-1)[2(D2-1)(D3-1)-D2-2] 1．     

广义Fibonacci立方体的网络容错性质分析

主要研究广义Fibonacci立方体的容错直径和宽直径,证明了n维Fibonacci立方体网络的k-1容错直径和k宽直径都是n-1,其中k=[n/3].     

广义超立方体网络中一类容错路由选择

证明了n-维广义超立方体网络Q(m1,m2,…,mn)中,任意两个节点x和y之间存在长度均不超过H(x,y)+2的m1+m2+…+mn-n条内点不交的路由,其中有H(x,y)条长度不超过H(x,y),此处H(x,y)表示x到y的汉明距离.并在此基础上讨论了广义超立方体网络的容错路由问题.证明了即使无效点很多,但只要存在某个(n-1)-维广义超子立方体中无效节点较少,则该n-维广义超立方体中的任意两个有效节点之间可以找到最优路由或接近最优路由的有效路由.     

超立方体网络的(d,k)控制数

(d,k)控制数是刻画容错网络中资源共亨可靠性的一个新参数.本文考虑了k维超立方体Qk的(d,k)控制数,得到:γ1,k(Qk)=2k-1(k>1);d=[k/2] 1(k>2)时,γd,k(Qk)=2;d≤[k/2](k≥4)时,3≤γd,k(Qk)≤2k-d 1;以及若d为正整数,且[k/d]=[k/(d-1)] 1,则γd,k(Qk)=γd,k(Qk),其中[k/d].d 1≤k1≤k.     

超方体(d,m)的控制数

This paper shows that the (d,m)-dominating number of the m-dimensional hypercube Qm(m≥4)is 2 for any integer d.([m/2] ≤d≤m).     

关于超立方体网络的(d,k)独立数

(d,k)独立数是分析互连网络性能的一个重要参数.对于任意给定的图G和正整数d和k,确定G的(d,k)独立数问题是一个NPC问题.因此,确定一些特殊图的(d,k)独立数显得很重要.本文确定了k维超立方体网络的(d,k)独立数等于2,如果d=k≥4或者d=k-1≥6 以及αd,k-t(Qk)=αd,k(Qk),其中0≤t≤k-2,1≤d≤k-t-1.     

广义Petersen图的宽直径

广义Petersen图是一类重要的并被广泛研究的互连网络。本文证明了广义Petersen图 P(m,2)的直径和3宽直径分别为O(m/4)和O(m/3)。     

故障加强超立方体中的边泛圈

本文研究了含故障点的加强超立方体圈嵌入的问题.利用构造的方法,获得了在至多具有n-2个故障点的n-维加强超立方体网络中每条非故障边均在长度从4到2ⁿ-2f的圈上,推广了超立方体网络中点容错圈嵌入的结果.     

带弦圈的最小2宽直径

设k为正整数,G是简单k连通图.图G的k宽直径,dk(G),是指最小的整数ι使得对任意两不同顶点x,y∈V(G),都存在k条长至多为ι的内部不交的连接x和y的路.用C(n,t)表示在圈Gn上增加t条边所得的图.定义h(n,t):min{d2(C(n,t))}.本文给出了h(n,2)=[n/2].而且,给出了当t较大时h(n,t)的界.     

纽立方体网络的容错泛圈性

互连网络包含所有可能长度的圈是一个重要的拓扑性质。纽立方体网络TOn是超立方体网络Qn的一种变型,其中n≥3是奇数。Chang等人[Information Science,113(1999),147-167]证明了TOn中包含任意长度为l的圈,其中4≤l≤2n。如果TOn中的故障点数和故障边数之和不超过(n-2),Huang等人[J.Parallel andDistributed Computing,62(2002),591-640]证明了:TQn中包含长度为2n-fv的圈,其中fv是故障点数。这篇文章改进这些结果为:TQn中包含任意长度为l的圈,其中4≤l≤2n-fv。     

Geodesic diameter of bodies of constant width

Let Φ a three-dimensional body of constant width B. Then the geodesic diameter G of the surface of Φ is estimated via B from above and from below. It is proved that G \leqslant \fracp2B G \leqslant \frac{\pi }{2}B , where an equality occurs and only if Φ is a body of revolution. Bibliography: 3 titles.     

Retracts of hypercubes

An induced subgraph G of a graph H is a retract of H if there is an edge-preserving map f from H onto G such that f|_G is the identity map on G. A median graph is a connected graph such that for any three vertices u,v and w, there exists a unique vertex x which lies simultaneously on some shortest (u,v)-, (v,w)-, and (w,u)-paths. It is shown that a graph G is a retract of some hypercube if and only if G is a median graph.     

Distance-preserving subgraphs of hypercubes

We give a characterization of connected subgraphs G of hypercubes H such that the distance in G between any two vertices a, b?G is the same as their distance in H. The hypercubes are graphs which generalize the ordinary cube graph.     

Symmetric edge-decompositions of hypercubes

We call a set of edgesE of the n-cubeQ _n a fundamental set for Q _n if for some subgroupG of the automorphism group ofQ _n , theG-translates ofE partition the edge set ofQ _n .Q _n possesses an abundance of fundamental sets. For example, a corollary of one of our main results is that if |E| =n and the subgraph induced byE is connected, then if no three edges ofE are mutually parallel,E is a fundamental set forQ _n . The subgroupG is constructed explicitly. A connected graph onn edges can be embedded intoQ _n so that the image of its edges forms such a fundamental set if and only if each of its edges belongs to at most one cycle.We also establish a necessary condition forE to be a fundamental set. This involves a number-theoretic condition on the integersa _j (E), where for 1 j n, a _j (E) is the number of edges ofE in thej ^th direction (i.e. parallel to thej ^th coordinate axis).     

Latin hypercubes and MDS codes

Maximum distance separable (MDS) codes have special properties that give them excellent error correcting capabilities. Counting the number of q-ary MDS codes of length n and distance d, denoted by D_q(n,d)_MDS, is a very hard problem. This paper shows that for d=2, it amounts to counting the number of (n-1)-dimensional Latin hypercubes of order q. Thus, D_q(3,2)_MDS is the number of Latin squares of order q, which is known only for a few values of q. This paper proves constructively that D₃(n,2)_MDS=6·2^n-2.     

The carvingwidth of hypercubes

The notion of the carvingwidth of a graph was introduced by Seymour and Thomas [Call routing and the ratcatcher, Combinatorica 14 (1994) 217-241]. In this note, we show that the carvingwidth of a d-dimensional hypercube equals 2^d-1.