关于稀疏图彩虹连通数的注记

• 全文链接
• 请求原文

作   者：

董九英;  李学良; 

作者机构：

江西财经大学统计学院;  南开大学组合数学中心; 

关键词：

彩虹着色;  度和条件σ_2(G);  彩虹连通数; 

期刊名称：

应用数学学报

基金项目：

网络设计中的图论方法
图的彩虹连通与广义连通度

i s s n：

0254-3079

年卷期：

2018 年 01 期

页   码：

134-137

摘   要：

一个边染色图G称为彩虹连通图如果图G中任意两个点有一条边染不同颜色的路相连.连通图G的彩虹连通数是使图G彩虹连通需要的最小颜色数,记为rc(G).我们依据Caro和Chakrabortyet等人的思想,研究了稀疏图的彩虹连通数,并得到了一些推广性的结果.我们证明了对于k≥2且G是一个阶为n有最小度δ(G)≥n/2-1+log_k n或最小度和σ_2(G)≥n-2+2log_k n的非完全图,那么rc(G)≤k.我们也研究了非完全偶图中rc(G)≤k的邻域条件,以及直径为2的图中rc(G)≤k的最小度条件.