小m条件下的联结数与分数(k,m)-消去图(英文)

设k,m为整数,其中k≥2,m≥0且k≥{2m-1,若k是奇数,2m-2,若k是偶数.本文证明:若图G满足n>4k+1-4(k+1-2m)～(1/2),bind(G)>((2k-1)(n-1))/(K(n-2)-2m+2),则G是分数(k,m)-消去图.当k是偶数时,若图G满足n>4k+1-4(k+2-2m)～(1/2),bind(G)>((2k-1)(n-1))/(K(n-2)-2m+3),则G是分数(k,m)-消去图.同时,本文所给结果在一定意思上是最好的.

独立集可去的分数(k,m)-消去图的最小度条件

图G称为分数(k,m)-消去图,若从G中删除任意m条边的剩余子图依然存在分数k-因子.称G是一个独立集可去的分数(k,m)-消去图,如果对G中任意独立集I,G-I是分数(k,m)-消去图.本文给出独立集可去的分数(k,m)-消去图的最小度条件,并说明结论是最好的.

特殊框架下分数(k,m)-一致图的联结数条件研究

计算机网络中数据传输的可行性可以用特殊条件下分数因子的存在性来衡量.而分数(k,m)-一致图是分数(k,m)-消去图和分数(k,m)-覆盖图的组合.即如果对于任意m条边的子图H,同时存在一个分数k-因子不包含H和另外一个分数k-因子,使得对任意e∈H有h(e)=1,则称为分数(k,m)-一致图.此外,联结数是计算机网络的重要参数,用来衡量网络的稳定性和易受攻击性.因此,通过对联结数和分数(k,m)-一致图的联系研究,给出了特定框架下分数(k,m)-一致图的联结数条件.

A Toughness Condition for Fractional(k, m)-deleted Graphs Revisited

In computer networks, toughness is an important parameter which is used to measure the vulnerability of the network. Zhou et al. obtains a toughness condition for a graph to be fractional(κ, m)-deleted and presents an example to show the sharpness of the toughness bound. In this paper, we remark that the previous example does not work and inspired by this fact, we present a new toughness condition for fractional(κ, m)-deleted graphs improving the existing one. Finally, we state an open problem.

关于独立集可去的分数(k,m)-消去图的度和条件的注记

图G称为分数(k,m)-消去图,若从G中删除任意m条边的剩余子图依然存在分数k-因子.称G是一个独立集可去的分数(k,m)-消去图,如果对G中任意独立集I,G-I是分数(k,m)-消去图.本文给出独立集可去的分数(k,m)-消去图的度和条件,并讨论了所得结论的最优性.

分数k-消去图的度条件

设G是一个图,若对于图G的任一边e,G-e都存在一个分数k-因子,则称G是一个分数k-消去图.证明了当顶点数、最小度以及max{dG(u),dG(v)}(其中u,v是图中任意两个不相邻顶点)满足一定条件时,G是分数k-消去图,该结论在一定意义上是最好的.

σ_2(G)与分数k-消去图

设G是一个图,若对于图G的任一边e,G-e都存在一个分数k-因子,则称G是一个分数k-消去图.对于非完全图,证明当顶点数、最小度以及σ2(G)满足一定条件时G是分数k-消去图.并说明结论在一定意义上是最好的.

联结数与分数k-消去图

设G是一个图,若对于图G的任一边e,G-e都存在一个分数k-因子,则称G是一个分数k-消去图.证明了若k≥2,bind(G)≥k且δ(G)≥k+1,则G是分数k-消去图.

特殊框架下分数(f,n',m)-临界消去图的联结数条件

设G是一个图,若去掉G中的任意n'个顶点的剩余子图仍是分数(f,m)-消去图,则称G是一个分数(f,n',m)-临界消去图.给出在a,b都是偶数的情况下分数(f,n',m)-临界消去图的两个联结数条件,并对条件的最好性进行了分析.

新框架下分数(g,f,n′,m)-临界消去图的领域并条件

若在图G中删除任意n′个顶点的剩余子图仍是分数(g,f,m)-消去图,则该图称为分数(g,f,n′,m)-临界消去图.给出在特定的函数框架下,分数(g,f,n′,m)-临界消去图的领域并条件.

全分数(g,f,n,m)-临界消去图的孤立韧度条件

作为衡量网络易受攻击性的参数,一个不完全图G的孤立韧度定义为I(G)=min{|S|/(i(G-S))|S■V(G),i(G-S)≥2},其中i(G-S)是G-S中孤立点的个数.否则对完全图定义I(G)=∞.本文研究孤立韧度和全分数(g,f,n,m)-临界消去图的关系,得到若I(G)>(b^(2)+an-Δ+m)/a,则图G是全分数(g,f,n,a m)-临界消去图,其中a,b是正整数,1≤a≤b,b≥2且Δ=b-a.本文得到的理论对网络设计有潜在的指导意义.最后我们以一个公开问题结束本文.

分数(g,f,n,m)-临界消去图的扩展联结数条件

分数因子作为因子的扩展,允许每一条边给0到1范围内的一个实数,并且要求每个顶点的分数度控制在某个范围内(由函数g和f的值决定,对应分数度的上下界).分数因子在通讯网络中有着广泛的应用,分数临界消去图可以用来衡量某一时刻网络受损时传输的可行性.联结数作为通讯网络的参数用来刻画网络的兼顾程度和易受攻击性能.本文主要给出一些关于分数(g,f,n,m)-临界消去图的扩展联结数条件.

图的联结数与分数κ-消去图

设G是一个图,若对于图G的任一条边e,G-e都存在一个分数k-因子,则称G是一个分数k-消去图.若k=2,则称分数k-消去图为分数2-消去图.本文证明了当bind(G)≥2,并且δ(G)≥3时,G是分数2-消去图.

从联结数角度看NFV网络中的资源调度条件

在资源调度网络中,资源调度的可行性等价于对应网络图中分数因子的存在性.研究特定图结构中分数因子的存在性可以帮助工程师设计和构建有效利用资源的网络.一个图称为全分数(g,f,n′,m)-临界消去图,如果从G中删除任何n′个顶点后,剩余的图仍然是全分数(g,f,m)-消去图.在本文中,我们给出两个使图成为全分数(g,f,n′,m)-临界消去图的联结数条件,并且通过例子说明结果是紧的.