图有较高连通度的一个充要条件

摘要

图的连通性理论是图论学科重要而基础的研究领域,通过该领域的研究,人们对图的结构和性质有了进一步的认识,并且将所得到的结果应用于网络设计、城市交通等实际问题中,取得了很多应用成果.例如,量化一个图或网络的脆弱程度,便始于图的连通性研究.因此,我们总是希望图能具有较高的连通度.对n个顶点的图G来说,当连通度不小于顶点数,n的一半时,我们认为这个图有较高的连通度.本文试图给出图具有较高连通度的一个充分必要条件.我们指出,对一个给定的正整数κ且κ≤n-2,有κ(c)≥n-κ成立当且仅当对顶点集V(C)的任意一对不交子集S和T,G[S,T]有一个完美匹配,这里|S|=|T|=κ,G[S,T]=G[s ∪T]-E(C[S])-E(C[T]).