极大3限制边连通图的充分条件  

Sufficient Conditions for Graphs to Be Maximally 3-Restricted Edge-Connected

作　　者：张磊[1] 

机构地区：[1]晋中学院数学学院,山西晋中

出　　处：《应用数学进展》2019年第3期381-388,共8页Advances in Applied Mathematics

基　　金：国家自然科学基金资助项目(61370001);晋中学院博士基金资助项目(bsjj2016202)。

摘　　要：k限 制 边 连 通 度 是 度 量 网 络 可 靠 性 的 重 要 参 数。 设G = (V, E)是 一 个 连 通 网 络。 称 一 个 边 集 合S ? E 是一个k限制边割,如果G ? S的每个连通分支至少有k个顶点。 称G的所有k限制边 割中所含边数最少的边割的基数为G的k限制边连通度,记为λk (G)。 定义ξk (G) = min{[X, Y ]:|X| = k,G[X]连通,Y = V (G)\X}。 称网络G是极大k限制边连通的,如果λk (G) = ξk (G)。 给出了网络是极大3限制边连通的一些充分条件。The k-restricted edge connectivity is an important index to measure the reliability of networks.For a connected network G=(V,E),an edge set S?E is a k-restricted edge cut if G?S is disconnected and every component of G?S has at least k vertices.The k-restricted edge connectivity of G,denoted byλk(G),is defined as the cardinality of a minimum k-restricted edge cut.Letξk(G)=min{|[X,Y]|:|X|=k,G[X]is connected},where Y=V\X.A connected network G is maximally k-restricted edge connected ifλk(G)=ξk(G).In this paper,some sufficient conditions are presented for networks to be maximally 3-restricted edge connected.

关 键 词：互连网络 极大3限制边连通图 3限制边连通度 围长 

分 类 号：O1[理学—数学]