王世英，王牟江山，冯凯，林上为，张明瑜

（1.山西大学 数学科学学院，山西 太原 030006；2.中国科学院 研究生院，北京 100049；3.山西大学 计算机与信息技术学院，山西 太原 030006）

＊图与补图孤立断裂度的关系

王世英1，王牟江山2，冯凯3，林上为1，张明瑜1

（1.山西大学 数学科学学院，山西 太原 030006；2.中国科学院 研究生院，北京 100049；3.山西大学 计算机与信息技术学院，山西 太原 030006）

连通图G的孤立断裂度isc（G）＝max｛i（G－S）－｜S｜∶S∈C（G）｝，其中i（G－S）是G－S中的孤立点数，C（G）是G的点割集.文章研究了图与补图孤立断裂度的关系.

网络；可靠性；孤立断裂度

0 引言

本文仅考虑简单图.设图G＝（V（G），E（G）），其中V（G）和E（G）分别为图G的顶点集和边集.若｜V（G）｜＝1，则称G为平凡图.设S⊂V（G）.当G是完全图时，若G－S是平凡图，称S是G的一个点割；当G是非完全连通图时，若G－S是不连通的，则称S是G的一个点割；G的连通度κ（G）为G的一个最小点割的顶点数.G的点割集C（G）＝｛S∶S是G的一个点割｝.G的分支数，奇分支数和孤立顶点数分别用ω（G），ω0（G）和i（G）表示.G的亏度def（G）是指G中未被G的一个最大匹配饱和的顶点数.下面是匹配理论中著名的 Tutte定理［1］.

定理1（Tutte定理［1］） 一个图G有完美匹配当且仅当对所有的S⊆V（G），有ω0（G－S）≤｜S｜成立.

1958年，Berge在Tutte定理的基础上给出了图G的一个最大匹配的精确刻画.特别的，他证明了def（G）＝max｛ω0（G－S）－｜S｜∶S⊆V（G）｝.此后，亏度这一参数得到许多学者的关注［2－5］.下面给出另一个著名的定理.

定理2［1］设S为哈密顿图G的一个顶点集合.则ω（G－S）≤｜S｜.

受该定理的启发，Jung［6］引进断裂度这一新概念来对图的哈密顿性进行讨论.

定义1［6］设G为一个连通图.图G的断裂度sc（G）＝max｛ω（G－S）－｜S｜∶S∈C（G）｝.

断裂度源于分数因子理论，近年来，它被普遍认为是度量图的……