图的强彩虹连通数

• 作者: 王万禹
• 来源期刊: 南宁师范大学学报（自然科学版）
• 关键词: 彩虹测地线 强彩虹连通数 边不交的圈
• 年，卷（期）: 2015,（2）
• 页码范围: 1-5
• 页数: 5页
• 分类号: O1575
• 语种: 中文

摘要

如果图G的任意两个顶点由一条路P连接，其中路P的每一条边着不同的颜色，则称图G为彩虹连通图。对图G的任意两个顶点u和v ，G的彩虹u － v测地线是一条长为d（u ，v ）的彩虹路，其中d（u ，v ）表示最短的u－ v路的长度。图 G称为强彩虹连通的如果对G的任意两点u和v间都存在一条彩虹u － v测地线。图G的强彩虹连通数是指使得图G是强彩虹连通而用的最少颜色的数目，用src（G ）表示。该文首先给出了一个含边不交的k‐圈图的一个强彩虹连通数的上界。接着给出了这个上界取等的充分条件。