摘要
图的限制弧连通度是度量网络可靠性的一个重要指标.设D是一个强连通有向图,其弧割S是一个限制弧割,若D-S包含一个非平凡的强连通分支D′,使得D-V(D′)包含至少一条弧.限制弧连通度λ′(D)是指最小限制弧割的弧数.一个强连通有向图是超级λ′的,若它的限制弧连通度是极大的且最小限制弧割的数目是极小的.定向图和二部定向图是超级λ′的最小度条件被给出,并用例子说明所给的条件是紧的.
The restricted arc connectivity of a digraph is an important measurement for reliability of a network. Let D be a digraph. An arc cut S is a restricted arc cut of D if D-S has a non-trivial strong component D′ such that D-V（D′） contains an arc. The restricted arc connectivity λ′（D） is the minimum cardinality over all restricted arc cuts. A strong digraph is super- λ′ if its restricted arc connectivity is maximal and the number of its minimumrestricted arc cuts is minimal. In this paper,we present some minimum degree conditions for（bipartition）orientedgraphs to be super-λ′ and give examples to show that our conditions are sharp.
出处
《河南科学》
2016年第2期157-160,共4页
Henan Science
基金
国家自然科学基金(61202017)
中国博士后基金(2012M510579)
关键词
网络
有向图
限制弧连通度
最小度
networks
digraph
restricted arc connectivity
minimum degree
