正则图的限制性边连通度

将连通图分离成阶至少为二的分支之并的边割称为限制性边割,最小限制性边割的阶称为限制性边连通度. 用λ′(G)表示限制性连通度,则λ′(G)≤ξ(G),其中ξ(G)表示最小边度. 如果上式等号成立,则称G是极大限制性边连通的. 本文证明了当k＞|G|/2时,k正则图G是极大限制性边连通的,其中k≥2, |G|≥4; k的下界在某种程度上是不可改进的.

Restricted Edge Connectivity of Regular Graphs

An edge cut that separates the connected graph into components with order at least two is restricted edge cut. The cardinality of minimum restricted edge cut is restricted edge connectivity. Denote by λ′(G) the restricted edge connectivity, then λ′(G)≤ξ(G) where ξ(G) is the minimum edge degree. G is called maximal restricted edge connected if the equality in the previous inequality holds. It is proved in this paper that: every k-regular connected graph G with k≥2 and |G|≥4 is maximal restricted edge connected if k>|G|/2. It is also exemplified that the lower bound of k in this proposition cannot be improved to some extent.