有向线图的限制性连通度

设D=（y（D），A（D））是一个强连通有向图．弧集S A（D）称为D的k-限制性弧割，如果D-S中至少有两个强连通分支的阶数大于等于后．最小k-限制性弧割的基数称为k-限制性弧连通度，记作Ak（D）．k-限制性点连通度Kk（D）可以类似地定义．有k-限制性弧割（k-限制性点割）的有向图称为λk-连通（kk-连通）有向图．本文研究有向图D的限制性弧连通度和其线图L（D）的限制性点连通度的关系，证明了对任意λk-连通有向图D，kk（L（D））≤λk（D），当k=2，3时等式成立；若L（D）是Kk（k-1）连通的，则λk（D）≤Kk（k-1）（L（D））；特别地，若D是一个定向图且L（D）是Kk（k-1）／2．连通的，贝0Ak（D）≤Kk（k-1），2（L（D））．

Restricted Connectivity of Line Digraphs

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 D - S has at least two strong components of order at least k. The k-restricted arc-connectivity λκ (D) is the minimum cardinality of all k-restricted arc-cuts. The concept of κ-restricted vertex-connectivity Kκ (D) can be defined similarly. A digraph which contains κ-restricted arc-cut (resp. κ-restricted vertex-cut) is called λκ-connected (resp. κκ-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 λκ-connected digraph D, Kκ(L(D)) ≤λk(D), equality holds when κ = 2,3; for any digraph D with L(D) being Kκ(κ-1)-connected, λκ(D) ≤ Kκ(κ-1)(L(D)); if D is an oriented graph such that L(D) is Kκ(κ-1)/2-connected, then λκ(D) ≤Kκ(κ-1)/2(L(D)).