Chordal Ring图CR_8k(1,3,9)的交叉数

The Crossing Number of Chordal Ring Graphs CR_8k(1,3,9)

摘要: 图的交叉数是图论中重要的一个分支，国内外诸多学者对图的交叉数这一问题进行广泛的关注和深入的研究。Garey和Johnson证明了确定图的交叉数问题是NP-完全问题，因此图的交叉数目问题仍然值得研究。但是由于探究和证明难度比较大，国内外对图的交叉数目问题的研究进展比较缓慢。至今为止，图的交叉数的研究成果集中在典型图类上，只得到了较少图族交叉数的精确值。本文主要采用数学归纳法和反证法研究了Chordal Ring图CR_8k(1,3,9)的交叉数。对于Chordal Ring图CR_8k(1,3,9)，给出一个交叉数为2k的好的画法，从而确定Chordal Ring图CR_8k(1,3,9)的上界。采用数学归纳法，以k=2时，cr(CR₁₆(1,3,9))=4为基础，假设k-1时，不等式cr(CR_8k(1,3,9))≥2(k-1)成立。采用反证法，将CR_8k(1,3,9)的边集分为不相交的2k组，讨论所有可能情形，证明了Chordal Ring图CR_8k(1,3,9)的下界。因此证明了：cr(CR8k(1,3,9))=2k(k≥2)。

Abstract: The crossing number of graphs is an important branch of graph theory. Many scholars at home and abroad have paid extensive attention to and studied the crossing number of graphs. Garey and Johnson proved that the problem of determining the number of intersects of graphs is NP-complete, so the problem of the number of intersects of graphs is still worth studying. However, due to the difficulty of exploration and proof, the research on the crossing number of graphs is slow at home and abroad. So far, the research results of graph crossing number focus on typical graph class, and only get the exact crossing numbers of very few families graphs. In this paper, a crossing number of chordal ring graphs CR_8k(1,3,9) are studied by mathematical induction and reduction. The upper bound of chordal ring graph CR_8k(1,3,9) is determined. By mathematical induction, on the basis of k=2, cr(CR₁₆(1,3,9))=4, and assuming k-1, the inequality is valid for cr(CR_8k(1,3,9))≥2(k-1). In this paper, the edge set of CR_8k(1,3,9) is divided into 2k groups with no intersection by the method of inverse proof, all possible cases are discussed, and the lower bound of CR_8k(1,3,9) of chordal ring graph is proved. It is thus proved that: cr(CR8k(1,3,9))=2k(k≥2) .