一些特殊图的Mycielskian图的彩虹顶点连通数

在寻找具有任意大色数但不含三角形的图类时,Mycielski发现了一类新的图变换,被称为图G的Mycielskian1]图,记为μ(G)。其定义如下:对于一个图G=(V,E),顶点集V(G)={v_1,v_2,…,v_n}。则图G的Mycielskian图的顶点集为V(G)∪V'(G)∪{u},其中V'(G)={x_1,x_2,…,x_n},μ(G)的边集E(μ(G))=E(G)∪{v_ix_j:v_iv_j∈E(G)}∪{x_iu:x_i∈V'(G)},其中i,j∈{1,2,?,n}。顶点x_i叫作v_i的复制点,顶点u叫作图μ(G)的根点。文章主要研究一些特殊图(如路、圈、完全图、星图、轮图、完全二部图等)的Mycielskian图的彩虹顶点连通数。最终推导并给出一类图的Mycielskian图的彩虹顶点连通数的一个上界。