孤立韧度变量和分数(k,n)-临界图

孤立韧度变量I′(G)是衡量网络健壮性的有效工具,定义|S|和i(G-S)-1的最小比值,其中S■V(G)满足i(G-S)>1。图G称为分数(k,n)-临界图,若从G中删除任意n个顶点,其剩余子图依然存在分数k-因子。文献[10]中得到分数k-因子存在性的紧I′(G)界。论文将文献[10]的结果推广到分数临界图,即:若δ(G)≥k+n且I′(G)>2k+n-1,则G是分数(k,n)-临界图,其中k≥2和n≥0是整数。

关于(ξ,k)-临界图

设 G为连通图 ,且ξ(G) =k≥ 1 ,若对 G中任意边 e,均有ξ(G\e) =k - 1 ,则称 G为 (ξ,k) -临界图 .本文刻划了ξ- 1 -临界图的若干性质 ,给出了一个图为ξ- 1 -临界图的一些充分或必要条件 ,以及一些ξ- 1 -临界图类 .

(g,f,k)-临界图的一个充分条件

设G是一个图,F是G的一个完全因子且ω(F)≥2,g和f是定义在V(G)上的两个整数值函数,且对所有的x∈V(G)有0≤g(x)<f(x).本文证明:若对F的每个分支C,G-V(C)是(g,f,k)-临界图,则G本身也是(g,f,k)-临界图.

(g,f,k)临界图的一个充分必要条件

设G是一个简单图,g和f是两个定义在V(G)上的整数值函数,且对所有的x∈V(G)都满足g(x)≤f(x).如果删除G的任何k个顶点后,图G的其余部分含有一个(g,f)因子,那么称图G为一个(g,f,k)-临界图.本文给出了一个图是(g,f,k)-临界图的一个充要条件,并对这些条件的应用作了讨论。进一步,本文研究了(g,f,k)-临界图的性质。

一个关于图是分数(k,n)-临界的邻域并条件

设G是一个图,以及k是满足1≤k的整数.一个图G在删除任意n个顶点后的子图均含有分数k-因子,则称G是一个分数(k,n)-临界图.给出了图是一个分数(k,n)-临界图的一个邻域并条件,并且该条件是最佳的.

(a,b,k)-临界图的一个充分条件

给出了一个图是(a,b,k)-临界图的孤立韧度条件,并证明该结论在一定意义下是最好的。