关于Mycielskian图的两个参数的结果

Two Parameters of Mycielskian Graphs

为了寻找一类具有任意大色数但不含三角形的图类,Mycielski[1]于1955年提出了一种有趣的图变换,由图G经过一种图变换得到的一个新图,我们称之为图G的Mycielskian图,记为μ(G).定义如下:设U=u1,…,un是图G的顶点集,U'={u'1,…,u'n}是图G的顶点的拷贝点集,u为μ(G)的根点.Mycielskian图的顶点是V(μ(G))=U∪U'∪{u},边集为E(μ(G))=E∪{uiu'j∶uiuj∈E}∪{u'iu∶u'i∈U'}这篇文章中,我们将给出图μ(G)的匹配数,独立数与原图G的匹配数和独立数之间的关系式.

Mycielski developed a graph transformation that transforms a graph G into a new graph μ(G),which is called the Mycielskian graph of G. For a graph G=(V,E),the Mycielskian of G is the graph μ(G),with the vertex set V(μ(G))= U ∪ U' ∪{u},where U'={u'1,…,u'n} and edge set E(μ(G))= E ∪{uiu'j∶ uiuj∈ E}∪{u'iu ∶ u'i∈ U'}..In this paper,we present the relations between independent number of α(μ(G))(or ν(μ(G)))of the Mycielskian graph μ(G)and α(G)(or ν(G))of graph G.