三阶边连通度最优性的一个充分条件

设G是有限简单无向图,D,g,δ分别表示G的直径、围长和最小度。设U是连通图G的边子集。如果G-U不连通,且每个连通分支至少有3个点,则称U是G的一个三阶限制边割,|U|的最小值称为G的三阶限制边连通度,记为λ3(G)。一个三阶连通子图的最小外度定义为ξ3(G)=min{|(X,X)|∶XV(G),|X|=3,G[X]连通}。证明如果D≤g-4且δ≥3,那么λ3(G)=ξ3(G)。

图的λ_3最优性的充分条件

设G=(V,E)是有限简单无向图,U是一个边割.若G-U的每个分支的阶至少是3,则称U为G的3阶限制边割.G的3阶限制边连通度λ3(G)是G的3阶限制边割之中最少的边数.设F是图G的一个子图,令(F)表示恰好有一个点在F上的边的数目,定义ζ3(G)=min{(F):F是G的3阶连通导出子图}.如果λ3(G)=ζ3(G),则称G是λ3最优的.本文给出了图的λ3最优性的一个充分条件.

二部图λ_3最优性的充分条件

本文给出了二部图λ3最优性的一些充分条件,它们在网络可靠性分析中有一定应用.