在寻找具有任意大色数但不含三角形的图类时,Mycielski发现了一类新的图变换,被称为图G的Mycielskian图,记为μ(G)。其定义如下:对于一个图G=(EE),顶点集V(G)={v1,v2,…,vn}。则图G的Mycielskian图的顶点集为V(G)∪V(G)∪{u),其中V(G)={x1,x2,…,xn},μ(G)的边集E(μ(G))=E(G)∪{vixj:vivj∈E(G)}∪{xiu:xi∈V'(G)},其中i,j∈{1,2,…,n}。顶点xi叫作vi的复制点,顶点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.