CAJ | 학술논문

设D=(V(D),A(D))是一个强连通有向图.弧集S A(D)称为D的κ-限制性弧割,如果D-S中至少有两个强连通分支的阶数大于等于κ.最小κ-限制性弧割的基数称为κ-限制性弧连通度,记作λκ(D).κ-限制性点连通度Kκ(D)可以类似地定义.有κ-限制性弧割(κ-限制性点割)的有向图称为λk-连通(Kκ-连通)有向图.本文研究有向图D的限制性弧连通度和其线图L(D)的限制性点连通度的关系,证明了对任意λκ-连通有向图D,Kκ(LD))≤λκ(D),当κ=2,3时等式成立;若L(D)是Kκ(κ-1)-连通的,则λκ(D)≤κκ(κ-1)(L(D));特别地,若D是一个定向图且L(D)是Kκ(k-1)/2-连通的,贝λκ(D)S ≤Kκ(κ-1)/2(L(D)).
설D=(V(D),A(D))시일개강련통유향도.호집S A(D)칭위D적κ-한제성호할,여과D-S중지소유량개강련통분지적계수대우등우κ.최소κ-한제성호할적기수칭위κ-한제성호련통도,기작λκ(D).κ-한제성점련통도Kκ(D)가이유사지정의.유κ-한제성호할(κ-한제성점할)적유향도칭위λk-련통(Kκ-련통)유향도.본문연구유향도D적한제성호련통도화기선도L(D)적한제성점련통도적관계,증명료대임의λκ-련통유향도D,Kκ(LD))≤λκ(D),당κ=2,3시등식성립;약L(D)시Kκ(κ-1)-련통적,칙λκ(D)≤κκ(κ-1)(L(D));특별지,약D시일개정향도차L(D)시Kκ(k-1)/2-련통적,패λκ(D)S ≤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 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)).