论文部分内容阅读
图的交叉数是图论的一个重要概念，它来源于20世纪五十年代Turan提出的“砖厂问题”(Turans brick factory problem).作为一个和图的非平面性、色数、亏格以及其它性质息息相关的参数，交叉数的研究发展至今，已经成为图论领域中非常重要的研究热点，由于求一般图的交叉数问题是-个NP-问题，因此到目前为止只对少数一些特殊图类有相关结果，
本文主要研究了Mycielski图的交叉数，得到了圈Cn的Mycielski图交叉数的相关结果，以及Mycielski图交叉数为0和1的充要条件，此外，我们还研究并证明了联图S4+Cn，S6+Cn和笛卡尔积图W5×Sn，S4×Wn，S5×Wn的交叉数。
在第一章中详细地介绍了交叉数的相关定义和符号，并回顾了交叉数的发展历史和现有的结果，以及一些公开问题，同时还简要总结了本文的基本内容，
在第二章中着重研究了Mycielski图的交叉数问题，第一节中证明了cr(M(Gn+1))≥cr(M(Cn))，并得到了n≤5时cr(M(Cn))的精确值.在第二节中得到了一些特殊图类的Mycielski图的交叉数，并证明了下述结果：
cr(M(G))=cr(G)=0当且仅当G为毛虫形或者C3；
cr(M(G))=1当且仅当G是Sn+e或者T(n；1,j2,…，jn-2)+e；
在第三章中研究了W5×Sn的交叉数，证明表示不超过x的最大整数)，还得到了W5的部分子图与Sn笛卡尔积的交叉数。