双广义Petersen图DP(7,1)的交叉数
The Crossing Number of Double Generalized Petersen Graph DP(7,1)
DOI: 10.12677/AAM.2023.123116, PDF,   
作者: 白 贺：辽宁师范大学数学学院，辽宁 大连
关键词: 交叉数；图；画法；Crossing Number； Graph； Drawing
摘要: 图的交叉数是图论的一个重要的分支，近百年以来，国内外诸多学者对于图的交叉数这一问题进行了广泛且深入的研究。事实上已证实确定一个图的交叉数问题是NP-完全问题。由于证明难度较大，国内外关于图的交叉数目问题的研究进展缓慢。本文主要采用反证法研究了双广义Petersen图DP(7,1)的交叉数，给出双广义Petersen图DP(7,1)的交叉数为7的一个好的画法。采用反证法，将图DP(7,1)的边集分为互不相交的7组，对所有可能情形进行讨论，从而确定交叉数的下界至少是7，得到图DP(7,1)的交叉数的精确值。
Abstract: The crossing number of graphs plays an important role in graph theory. In the last hundred years, many scholars have conducted extensive and in-depth research on the problem of graph crossing numbers at home and abroad. In fact, a number of scholars have proved that determining the crossing number of a graph is a NP-complete problem. Due to the difficulty of proof, scholars at home and abroad have experienced a difficult process in the field of the crossing numbers. This pa-per mainly studies the crossing number of double generalized Petersen graph DP(7,1) and use proof by contradiction; a drawing of a crossing number of 7 for the double generalized Petersen graph DP(7,1) is given by the definition of a good drawing. Firstly, the edge sets of graph DP(7,1) are divided into 7 groups that do not intersect each other; secondly, all possible cases are discussed to determine that the lower bound of the crossing number of graph DP(7,1) is at least 7; finally, the exact value of the crossing number of graph DP(7,1) is obtained.
文章引用：白贺. 双广义Petersen图DP(7,1)的交叉数[J]. 应用数学进展, 2023, 12(3): 1141-1151. https://doi.org/10.12677/AAM.2023.123116

参考文献

[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. The Bulletin of the Malaysian Mathematical Society, 7, 68-72.
[4] Guy, R.K. (1969) Proof Techniques in Graph Theory. Academic Press, New York.
[5] Blazer, J and Koman, N. (1964) Theory of Graphs and Its Applications. Academic Press, New York.
[6] Kieitman, D.J. (1970) The Crossing Number of K5,n. Combinatrial Theory (Series B), 9, 315-325. [Google Scholar] [CrossRef] 
[7] Pan, S. and Richter, R.B. (2007) The Crossing Number of K11 Is 100. Journal of Graph Theory, 56, 128-134. [Google Scholar] [CrossRef] 
[8] Mcquillan, D., Pan, S. and Richter, R.B. (2010) On the Crossing Number of K13. Journal of Combinatorial Theory, 115, 224-235. [Google Scholar] [CrossRef] 
[9] Aichholzer, O., Aurenhammer, F. and Krasser, H. (2002) On the Crossing Number of Complete Graphs. Proceedings of the 18th Annual Symposium on Computational Geometry, Barcelona, 5-7 June 2002, 19-24. [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 Pe-tersen Graph. Discrete Mathematic, 30, 221-242. [Google Scholar] [CrossRef] 
[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] 林晓惠. 图论中若干难题的研究[D]: [博士学位论文]. 大连: 大连理工大学, 2004.
[14] 马登举, 任韩, 卢俊杰. 广义Petersen 图G(2m+1, m)的交叉数[J]. 华东师范大学学报(自然科学版), 2005(1): 34-39.
[15] Lin, X.H., Yang, Y.S., Zheng, W.P., et al. (2009) The Crossing Number of General-ized Petersen Graphs with Small Order. Discrete Applied Mathematics, 157, 1016-1023. [Google Scholar] [CrossRef] 
[16] 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] 
[17] Zhou, J.X. and Feng, Y.Q. (2012) Cubic Vertex-Transitive Non-Cayley Graphs of Order 8p. Electronic Journal of Combinatorics, 19, 453-472. [Google Scholar] [CrossRef] 
[18] 郑百功. 冒泡排序图Bn和双广义Petersen图P(10, 3)的交叉数[D]: [硕士学位论文]. 大连: 大连理工大学, 2013.

为你推荐