叶形图的广义连通度

The Generalized Connectivity of Leaf-Sort Graphs

摘要: 一个互联网络系统通常会被构建成一个无向连通图G=(V,(G),E(G))，其中V,(G)代表了图的顶点集，E(G)代表着图的边集，顶点和边分别代表着互联网络中的处理器和处理器之间的通信链路。在互联网络中，处理器或者通信链路出现故障是不可避免的，而连通性在衡量互联网络的容错性和可靠性方面起着重要作用。本文我们主要研究一个图G的广义k-连通性。对于图G的一个顶点子集S，k(s)表示图G中边互不相交树T₁,T₂,...,T_r的最大数量r，这些树须满足，这一条件。对于任意的2≤k≤n，图G的广义k-连通度κ_k(G)被定义为：。叶形图是一个重要的凯莱图，它有许多非常好的性质。在这篇文章中，我们主要研究了n维叶形图CFn的广义3-连通度，证明了 (n为大于等于3的奇数)； (n为大于等于4的偶数)。

Abstract: An interconnection network is usually modeled as an undirected, connected graph G=(V,(G),E(G)) , where V,(G) represents vertex set, E(G) represents edge set, and nodes rep-resent processors, edges represent communication links between processors. In the interconnect network, the failure of processors or communication links is unavoidable. The connectivity plays an important role in measuring the fault tolerance and reliability of interconnection networks. This paper, we mainly study the generalized k-connectivity of a graph G. For any S⊆V(G), let k(s) denote the maximum number of edge-disjoint trees T₁,T₂,...,T_r in G such that for any i,j∈[i,r] and i ≠ j. For every 2≤k≤n , the generalized k-connectivity κ_k(G) is defined as . An n-dimension leaf sort graph CF_nis an important Cayley graph, it has many good properties. In this paper, we mainly study the gen-eralized k-connectivity of CF_n , proved that: when n is odd, ; when n is even, .