有向线图的限制性连通度(英文)

Restricted Connectivity of Line Digraphs

设D=(V(D),A(D))是一个强连通有向图.弧集S(?)A(D)称为D的k-限制性弧割,如果D-S中至少有两个强连通分支的阶数大于等于k.最小k-限制性弧割的基数称为k-限制性弧连通度,记作λ_k(D).k-限制性点连通度κ_k(D)可以类似地定义.有k-限制性弧割(k-限制性点割)的有向图称为λ_k-连通(κ_k-连通)有向图.本文研究有向图D的限制性弧连通度和其线图L(D)的限制性点连通度的关系,证明了对任意λ_k-连通有向图D,κ_k(L(D))≤λ_k(D),当k=2,3时等式成立;若L(D)是κ_(k(k-1))-连通的,则λ_k(D)≤κ_(k(k-1))(L(D));特别地,若D是一个定向图且L(D)是κ_(k(k-1)/2)-连通的,则λ_k(D)≤κ_(k(k-1)/2)(L(D)).

For a strongly connected digraph D = （V（D）, A（D））, an arc-cut S A（D） is a k-restricted arc-cut of D if O - S has at least two strong components of order at least k. The k-restricted arc-connectivity λk （D） is the minimum cardinaiity of all k-restricted arc-cuts. The concept of k-restricted vertex-connectivity kk （D） can be defined similarly. A digraph which contains k-restricted arc-cut （resp. k-restricted vertex-cut） is called λk-connected （resp. kk-connected）. In this paper, we study the relationship between the restricted arc-connectivity of digraph D and the restricted vertex-connectivity of its line digraph L（D）. We prove that for any λk-connected digraph D, kk（L（D）） ≤λk（D）, equality holds when k = 2, 3; for any digraph D with L（D） being kk（k-1）-connected, λk（D） ≤kk（k-1）（L（D））; if D is an oriented graph such that L（D） is kk（k-1）/2-connected, then λk（D） ≤ nk（k-1）/2（L（D））.