直径为2的有向图的彩虹连通

On Rainbow Connection of Digraphs with Diameter 2

利用概率方法证明:直径为2的有向图D的彩虹数cr→(D)∈{2,3,4,5},直径为2的k-正则有向图D的强彩虹数scr→(D)≤[(e(4_(μ2)k-2_(μ2)+1))1/μ1],并且存在无穷多个满足cr→(D)=scr→(D)=2的有向强正则图.

In this paper,by the probabilistic method,we prove that for any digraphs D with diameter 2,its rainbow connection numbercr→（D）∈ {2,3,4,5},for any k-regular directed graph D with diameter 2,scr→（D）≤[（e（4μ2k-2μ2＋1））1/μ1],and there exist infinite directed strongly regular graphs satisfingcr→（D）=scr→（D）=2.