广义Petersen图P(4k,4)的交叉数
The Crossing Number of Generalized Petersen Graph P(4k,4)
DOI: 10.12677/AAM.2022.1111827, PDF,   
作者: 卢 妮：辽宁师范大学，辽宁 大连
关键词: 交叉数；好画法；广义Petersen图；Crossing Number； Good Drawing； Generalized Petersen Graph
摘要: 图的交叉数是图论中一个重要的部分，近百年来，国内外很多学者都对图的交叉数这一问题进行研究。由于证明难度较大，国内外关于图的交叉数领域的研究进展缓慢。本文主要对广义Petersen图P(4k,4)的交叉数进行研究。采用反证法和数学归纳法，将P(4k,4)的边集分成边不相交的4k组，讨论所有可能情况，从而证得P(4k,4)(k≥4)的交叉数的下界至少是2k。
Abstract: The crossing number of graphs is an important part of graph theory. In the past 100 years, many scholars at home and abroad have studied the problem of the crossing number of graphs. Due to the difficulty of proof, the research progress in the field of the crossing numbers at home and abroad is slow. This paper mainly studies the crossing number of generalized Petersen graph P(4k,4). The method of proof by contradiction and mathematical induction are adopted, the edge set of P(4k,4) is divided into 4k groups with disjoint edges, and discuss all possible situations to prove that the lower bound of the crossing number of P(4k,4)(k≥4) is at least 2k.
文章引用：卢妮. 广义Petersen图P(4k,4)的交叉数[J]. 应用数学进展, 2022, 11(11): 7828-7836. https://doi.org/10.12677/AAM.2022.1111827

参考文献

[1] Turan, P. (1997) A 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, 1, 312-316. [Google Scholar] [CrossRef] 
[3] Guy, R.K. (1960) A Combinatorial Problem. Malaysian Mathematical Society, 7, 68-72.
[4] Guy, R.K. (1969) Proof Techniques in Graph Theory. Academic Press, New York.
[5] Kieitman, D.J. (1970) The Crossing Number of K5,n. Combinatorial Theory (Series B), 9, 315-325. [Google Scholar] [CrossRef] 
[6] Aichholzer, O., Aurenhammer, F. and Krasser, H. (2002) On the Crossing Number of Complete Graphs. Proceedings of the Eighteenth Annual Symposium on Computational Geometry, Barcelona, 5-7 June 2002, 19-24. [Google Scholar] [CrossRef] 
[7] Zarankiewicz, K. (1954) On a Problem of P. Turan Concerning Graphs. Fundanmenta Mathematicae, 41, 137-145. [Google Scholar] [CrossRef] 
[8] Woodall, D.R. (1993) Cyclic-Order Graphs and Zarankiewicz’s Crossing Number Conjecture. Journal of Graph Theory, 17, 657-671. [Google Scholar] [CrossRef] 
[9] Nahas, N. (2003) On the Crossing Number of Km,n. The Electronic Journal of Combinatorics, 10, 1-6. [Google Scholar] [CrossRef] 
[10] Exoo, G., Harary, F. and Kabell, J. (1981) The Crossings of Some Generalized Petersen Graphs. Mathematica Scandinavica, 48, 184-188. [Google Scholar] [CrossRef] 
[11] Fiorini, S. (1986) On the Crossing Number of Generalized Petersen Graph. Discrete Mathematic, 30, 221-242.
[12] Richter, R.B. and Salazar, G. (2002) The Crossing Number of P(N, 3). Graphs and Combinatorics, 18, 381-394. [Google Scholar] [CrossRef] 
[13] Sarazin, M.L. (1997) The Crossing Number of the Generalized Petersen Graph P(10, 4). Mathematica Slovaca, 47, 189-192.
[14] Salazar, G. (2005) On the Crossing Number of Loop Networks and Generalized Petersen Graphs. Discrete Mathematic, 302, 243-253. [Google Scholar] [CrossRef] 
[15] 林晓惠. 图论中若干难题的研究[D]: [博士学位论文]. 大连: 大连理工大学, 2004.
[16] 马登举, 任韩, 卢俊杰. 广义Petersen图G(2m+1, m)的交叉数[J]. 华东师范大学学报(自然科学版), 2005(1): 34-39.
[17] Lin, X.H., Yang, Y.S., Zheng, W.P., et al. (2009) The Crossing Number of Generalized Petersen Graphs with Small Order. Discrete Applied Mathematics, 157, 1016-1023. [Google Scholar] [CrossRef] 
[18] Fiorini, S. and Gauci, J.B. (2003) The Crossing Number of the Generalized Petersen Graph P(3k, k). Mathematica Bohemica, 128, 337-347. [Google Scholar] [CrossRef] 
[19] 郑百功. 冒泡排序图 和广义Petersen图P(10,3)的交叉数[D]: [硕士学位论文]. 大连: 大连理工大学, 2013.

为你推荐