2-连通图的修正的彩虹顶点连通数  

Revised rainbow vertex-connection number of 2-connected graphs

作　　者：王万禹 

机构地区：[1]成都师范学院数学学院,四川成都611130

出　　处：《陕西师范大学学报（自然科学版）》2017年第6期19-21,共3页Journal of Shaanxi Normal University：Natural Science Edition

基　　金：四川省教育厅自然科学基金(15ZB0346);成都师范学院科研基金(CS14ZB06)

摘　　要：路P称为修正的顶点彩虹路,如果P中所有的顶点着不同的颜色或者除端点外其余顶点着不同于端点的颜色。图G称为是修正的彩虹顶点连通的,如果对于G的任意两个顶点u和v,G都有一条修正的彩虹顶点u-v路。使图G是修正的彩虹顶点连通图的最小颜色数目k称为图G的修正的彩虹连通数,记做rvc*(G)。给出了2-连通图G的修正的彩虹顶点连通数的一个上界,即rvc*(G)≤|n/2|+1。A path of Gis a rainbow path if all of its vertices have distinct colors or its internal vertices have distinct colors.In other words,the endpoints have the same colors.If for every pair u,vof distinct vertices,Gcontains a revised rainbow vertex u-v path,then Gis revised rainbow vertex-connected.The minimum number k of Gthat results in a revised rainbow vertex-connected graph is called the revised rainbow vertex-connection number of G,denoted by rvc^＊（G）.It is proved that rvc^＊（G）≤｜n/2｜＋1 for 2-connected graphs.

关 键 词：修正的彩虹顶点连通数 彩虹顶点着色 

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