玫瑰花窗图R3k+2(1,3)的交叉数

图论是离散数学的一个重要分支,是一门研究图的学问,而图的交叉数也是图论中的一个重要的研究方向,国内外诸多学者都对图的交叉数问题展开了相关研究。玫瑰花窗图是广义周期图的一类延伸,本文针对玫瑰花窗图的交叉数展开研究,给出了玫瑰花窗图R3k+2(1,3)的相关定义,找到了R3k+2(1,3)的一个好的画法,得到了R3k+2(1,3)的交叉数的上界。最后利用数学归纳法和反证法得到了玫瑰花窗图R3k+2(1,3)的交叉数的下界,进而完成了证明。

一类小阶图的交叉数

图的交叉数的研究已经有几十年的历史,Garey和Johnson证明了确定一个图的交叉数是NP-完全问题。由于证明难度较大,国内外关于图的交叉数领域的研究进展缓慢。本文令cr(G)表示图G的交叉数,主要利用循环图C(16, 4)的一个分解{F1, F2, F12}对其交叉数进行研究。首先给出C(16, 4)交叉数为8的好的画法,得到交叉数的上界。然后采用反证法,将C(16, 4)的边集分成边不相交的3组,讨论所有可能情况,从而证得C(16, 4)的交叉数的下界。