有向图是极大弧连通的充分条件

Digraphs Are Sufficient Conditions for Maximum Arc Connected

设D是一个n阶强连通的有向图.D的逆度定义为,R(D)=∑v∈V(D)max{1/(d+(v)),1/(d-(v))},其中,d+(v)与d-(v)是v的出度和入度.证明了,如果R(D)<2+2/(δ(δ+1))+(n-2δ)/((n-δ-2)(n-δ-1)),其中,δ(D)=min{d+(v),d-(v),v∈V(D)},是最小度,那么,D是极大弧连通的.同时,给出了一个二部图的类似结果.

Let D be an n-order strongly connected digraphs.The inverse degree of D is defined by R（D）=∑v∈V（D）max{1/（d^＋（v））,1/（d^-（v））} where d^＋（v） and d^-（v） is in-degree and out-degree of v respectively.If R（D）〈2＋2/δ（δ＋1）＋n-2δ/（n-δ-2）（n-δ-1） is testified where δ（D）=min{d^＋（v）,d^-（v）,v∈V（D）} is the minimum degree,then D is maximally arc-connected.Analogous results for bipartite digraphs were given.