论文部分内容阅读
对任意的一个图G，Chartrand et al.在[9]这篇文章中定义了图的彩虹连通数和强彩虹连通数。给一个图的边着色，如果图上任两个顶点间都有一条边色不同的路相连，则称图G为彩虹连通的。使得图G能彩虹连通的最小所需的颜色数称为G的彩虹连通数，记为rc(G).给一个图的边着色，如果图上任两个顶点间都有一条边色不同的路相连，且这条路为两个顶点间的最短路，则称图G为强彩虹连通的。使得图G能强彩虹连通的最小所需的颜色数称为G的强彩虹连通数，记为src(G).作者计算了一些图类的彩虹连通数和强彩虹连通数，最后提出了一个猜想：对于任意正整数a和6，存在一个连通图G满足：rc(G)=a和src(G)=b当且仅当a=6∈{1，2}或者3≤a≤b。在本论文中主要讨论这个猜想，并给出一个图的构造，使得上面的这个猜想成立。