图的弱毁裂度与网络抗毁性

刘 勇, 杨淑姝, 魏宗田, 岳 超

(西安建筑科技大学理学院，西安 710055)

1 引言

网络的广泛使用和中断的频繁发生，使得抗毁性与可靠性研究愈发重要.连通度与边连通度可以刻画图的结构特征，但这两个参数考虑的是在最坏情形下破坏网络的难易程度[1-3].后来一些新的参数不断被引入[4-7]，用以度量网络抗毁性.这些参数既考虑了破坏网络的难度，又反映了网络被破坏的程度.但是它们的侧重点各不相同，因而至今没有度量网络抗毁性的统一标准.

弱毁裂度是一个视角较为全面的抗毁性参数.设G是一个简单连通图，其弱毁裂度定义为[8]

其中X表示G的点割集，ω(G-X)和me(G-X)分别表示G-X的连通分支数和最大分支中的边数.若存在X*⊂V(G)，使得rw(G) =ω(G-X*)-|X*|-me(G-X*)，则称X*为G的一个rw-集.

本文通过研究该参数的性质和取值范围，以及Nordhaus-Gaddum(N-G)型问题，揭示图的弱毁裂度与网络结构之间的关系.

2 弱毁裂度与图的结构

图(网络)的抗毁性参数有很多，这些参数与图的基本参数之间的关系，在很大程度上反映了图的结构特征.下面给出图的弱毁裂度与其它基本参数之间的关系，也可以看作是弱毁裂度的界，是估计一般图的弱毁裂度大小的重要工具.

定理1 设G是周长为c(c ＞0)的n(n ≥4)阶连通图，则rw(G)≤n-c.

证明 设C为G的一个最长圈，即|V(C)| =c.若X为G的一个点割集，则在GX中，至多有n-c个分支包含V(G) V(C)中的点；至多有|V(C)∩X|个分支包含V(C)中的点.从而ω(G-X)≤|V(C)∩X|+n-c.

另一方面，由于|X|≥|V(C)∩X|, me(G-X)≥0，则由定义可知

定理得证.

注1 设G是将圈C2k的一个点与星图S1,n-2k的中心点重合所得之图，其中k ≥2, n ≥2k，则rw(G)=n-c.这表明……