一类小阶图的交叉数
The Crossing Number of a Class of Small-Order Graphs
DOI: 10.12677/PM.2023.1310319, PDF,   
作者: 鲁东岳：辽宁师范大学数学学院，辽宁 大连
关键词: 交叉数；循环图；好的画法；Crossing Number； Cyclic Graphs； Good Drawing
摘要: 图的交叉数的研究已经有几十年的历史，Garey和Johnson证明了确定一个图的交叉数是NP-完全问题。由于证明难度较大，国内外关于图的交叉数领域的研究进展缓慢。本文令cr(G)表示图G的交叉数，主要利用循环图C(16, 4)的一个分解{F1, F2, F12}对其交叉数进行研究。首先给出C(16, 4)交叉数为8的好的画法，得到交叉数的上界。然后采用反证法，将C(16, 4)的边集分成边不相交的3组，讨论所有可能情况，从而证得C(16, 4)的交叉数的下界。
Abstract: 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.
文章引用：鲁东岳. 一类小阶图的交叉数[J]. 理论数学, 2023, 13(10): 3088-3094. https://doi.org/10.12677/PM.2023.1310319

参考文献

[1] Turan, P.A. (1997) Note of Welcome. Journal of Graph Theory, 1, 7-9. [Google Scholar] [CrossRef] 
[2] Garey, M.R. and Johnson, D.S. (1993) Crossing Number Is NP-Complete. SIAM Journal on Algebraic & Discrete Methods, 4, 312-316. [Google Scholar] [CrossRef] 
[3] Guy, R K. (1960) A Combinatorial Problem. Malayan Math. Soc., 7, 68-72.
[4] Guy, R.K. (1969) Proof Techniques in Graph Theory. Academic Press, New York.
[5] Kleitman, D.J. (1970) The Crossing Number of K5,n. Journal of Combinatorial Theory, 9, 315-325. [Google Scholar] [CrossRef] 
[6] Pan, S. and Richter, R.B. (2007) The Crossing Number of K11 Is 100. Journal of Graph Theory, 56, 128-134. [Google Scholar] [CrossRef] 
[7] McQuillan, D., Pan, S.J. and Bruce Richter, R. (2015) On the Crossing Number of K13. Journal of Combinatorial Theory Series B, 115, 224-235. [Google Scholar] [CrossRef] 
[8] Balogh, J., Lidicky, B. and Salazar, G. (2019) Closing in On Hill’s Conjecture. SIAM Journal on Discrete Mathematics, 33, 1261-1276. [Google Scholar] [CrossRef] 
[9] Fiorini, S. (1986) On the Crossing Number of Generalized Petersen Graphs. North-Holland Mathematics Studies, 123, 225-241. [Google Scholar] [CrossRef] 
[10] 郝荣霞, 刘彦佩. 关于循环图交叉数的新上界(英文) [J]. 运筹学学报, 1999(3): 1-6.

为你推荐