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

The Rainbow Vertex-Connection Number of Mycielskian Graph of Some Special Graphs

在寻找具有任意大色数但不含三角形的图类时,Mycielski发现了一类新的图变换,被称为图G的Mycielskian[1]图,记为μ(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图的彩虹顶点连通数的一个上界。

In search for a class of graphs with arbitrary chromatic number but not containing triangles, Mycielski developed a graph transformation that transforms a graph Gintoa new graph μ（G）, which is called the Mycielskian of G. The definition is as follows： For a graph G = （V,E）, where V（G）={v1,v2,…,vn}. The Mycielskian of G is thegraph μ（G） with vertex set V（G）∪V（G）∪{u）, where V（G）={x1,x2,…,xn} and edge set E（μ（G））=E（G）∪{vixj：vivj∈E（G）}∪{xiu：xi∈V＇（G）}.The vertex xi is called the twin of the vertex v,（and v,the twin of x,） and the vertex u is called the root of μ（G）. In this paper, the rainbow vertex-connection numbers on Mycielskian graph of path, cycle, complete graph, star, wheel and complete bipartite graph are presented.