一类小阶图的交叉数  

The Crossing Number of a Class of Small-Order Graphs

作　　者：鲁东岳 

机构地区：[1]辽宁师范大学数学学院,辽宁 大连

出　　处：《理论数学》2023年第10期3088-3094,共7页Pure Mathematics

摘　　要：图的交叉数的研究已经有几十年的历史,Garey和Johnson证明了确定一个图的交叉数是NP-完全问题。由于证明难度较大,国内外关于图的交叉数领域的研究进展缓慢。本文令cr(G)表示图G的交叉数,主要利用循环图C(16, 4)的一个分解{F1, F2, F12}对其交叉数进行研究。首先给出C(16, 4)交叉数为8的好的画法,得到交叉数的上界。然后采用反证法,将C(16, 4)的边集分成边不相交的3组,讨论所有可能情况,从而证得C(16, 4)的交叉数的下界。Cross numbers of graphs have been studied for decades, Garey and Johnson demonstrated that determining the cross numbers of a graph is an NP-complete problem. Because of the difficulty of proof, the research on the cross number of graphs at home and abroad is slow. In this paper, the cross number of a graph G is represented cr(G), and the cross number is studied by using a de-composition C(16, 4) of a cyclic graph C(16, 4). First of all, a good drawing of the cross number of 8 is given, and the upper bound of the cross number is obtained. Then we divide the edge set of C(16, 4) into 3 groups with disjoint edges, discuss all possible cases, and obtain the lower bound of the cross number.

关 键 词：交叉数 循环图 好的画法 

分 类 号：G63[文化科学—教育学]