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

On Rainbow Connection of Digraphs with Diameter 2

作　　者：龙汉青 于克凡 张必成 

机构地区：[1]湘潭大学数学与计算科学学院,湖南湘潭411105

出　　处：《湘潭大学自然科学学报》2018年第1期40-43,共4页Natural Science Journal of Xiangtan University

基　　金：湖南省大学生研究性学习和创新性实验计划项目C2017XTUSJ016)

摘　　要：利用概率方法证明:直径为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.

关 键 词：彩虹连通 直径为2的有向图 有向强正则图 概率方法 

分 类 号：O157.5[理学—数学]