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

董九英1 李学良2

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

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