一类可传递分解图的交叉数

The Crossing Number of a Class of Transitive Decomposition Graphs

摘要: 图的交叉数是拓扑图论中重要的一个分支，国内外诸多学者对图的交叉数这一问题进行广泛的关注和深入的研究，Garey和Johnson证明了计算图的交叉数是NP-完全问题。本文令cr(G)表示图G的交叉数，主要利用弱积图C_n × K₃的一个传递分解{H₁,H₂,...H_n}对其交叉数进行研究。首先构造了六边形图C2k × K3交叉数较少的画法，给出交叉数的上界，然后采用数学归纳法和反证法，将C_2k × K₃的边集分成边不相交的2k组，讨论所有可能情况，从而证得cr(C_2k × K₃) = 4k，k ≥ 3。

Abstract: The crossing number of graphs is an important branch of topological graph theory. Many scholars at home and abroad have made extensive attention and in-depth research on the crossing number of graphs. Garey and Johnson proved that the calculation of the crossing number of graphs is a NP-complete problem. In this paper, let cr(G) denote the crossing number of a graph G, we study the crossing number of C_n × K₃ by using a transitive decomposition {H₁,H₂,...H_n} . First, we construct a method of drawing the hexagon graph C_2k × K₃ with less crossing number, and give the upper bound of the crossing number. Then, the edge set of C2k × K3 is divided into 2k groups with disjoint edges by mathematical induction and reduction to absurdity. All possible cases are discussed, and cr(C_2k × K₃) = 4k, k ≥ 3 is proved.