折叠交叉立方体的限制连通度

Restricted Connectivity of Folded Crossed Cubes

限制性连通度作为评估互联网络容错性的最佳参数之一,在多处理器系统中对可靠性计算起着重要作用.给定一个连通图G=(V,E)和一个非负整数h,子集F■V(G)(F■E(G))(如果存在)称为h-限制点割(h-限制边割),如果G-F不连通,并且G-F中的每个连通分支至少有h+1个顶点,其中最小的h-限制点割(h-限制边割)的基数称为图G的h-限制连通度(h-限制边连通度),记为κ_(h)(G)(λ_(h)(G)).本文确定了h=2时n-维折叠交叉立方体FCQ_(n)的κ_(h)(G)和λ_(h)(G).

As one of the best parameters to evaluate the fault tolerance of interconnection networks,restricted connectivity plays an important role in multiprocessors systems for reliable computing.Given a connected graph G=(V,E)and a non-negative integer h,a subset F■V(G)(F■E(G))of G,if any,is called h-restricted vertex cut(h-restricted edge cut)of G,if G-F is disconnected and every component of G-F has at least h+1 vertices,the cardinality of a minimum h-restricted vertex cut(h-restricted edge cut)of G is the h-restricted connectivity(h-restricted edge connectivity)of G,and denoted by κ_(h)(G)(λ_(h)(G)).We determine κ_(h)(G)(λ_(h)(G))of the folded crossed cube FCQ_(n) for h=2.