关于循环图C(10,3)的交叉点
On the Crossing Points of Circulant Graphs C(10,3)
DOI: 10.12677/AAM.2023.1212515, PDF,   
作者: 高 琳：辽宁师范大学数学学院，辽宁 大连
关键词: 交叉数；循环图；好画法；去边数；Crossing Number； Circulant Graph； Good Drawing； Removal Number
摘要: 众所周知，确定循环图交叉数的精确值是非常困难的。即便如此，在这一领域的一些重要结果仍然得到了证明。C(10,3)作为C(3m + 1,3) (m ≥ 3)这一类循环图的证明基础，本文证明了在C(10,3)的最优画法中，主圈上的边最多自交1次。
Abstract: It is well known that determining the exact values of crossing number for circulant graphs is very difficult. Even so, some important results in this field are still proved. C(10,3) as the basis for the proof of C(3m + 1,3) (m ≥ 3), in this paper, we prove that the edges from the principal circle of C(10,3) cross each other at most once in an optimal drawing.
文章引用：高琳. 关于循环图C(10,3)的交叉点[J]. 应用数学进展, 2023, 12(12): 5241-5253. https://doi.org/10.12677/AAM.2023.1212515

参考文献

[1] Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmilan Ltd. Press, New York.
[2] Mohar, B. and Thomassen, C. (2001) Graphs on Surfaces. Johns Hopkins University Press, Baltimore. [Google Scholar] [CrossRef] 
[3] Garey, M.R. and Johnson, D.S. (1983) Crossing Number Is NP-Complete. SIAM Journal on Algebraic Discrete Methods, 4, 312-316. [Google Scholar] [CrossRef] 
[4] Hao, R.X. and Liu, Y.P. (1999) New Upper Bounds on Crossing Number of Circular Graph. OR Transactions, 3, 1-6.
[5] Lu, J.J., Ren, H. and Ma, D.J. (2004) On the Crossing Number of C(m, 3). Journal of Systems Science and Mathematical Sciences, 24, 504-512.
[6] Lu, J.J., Wu, Y.R. and Ren, H. (2005) Crossing Number of Certain Circular Graphs. Journal of East China Normal University, 16-22.
[7] Lin, X.H., Yang, Y.S., Lv, J.G. and Hao, X. (2005) The Crossing Number of C(mk;{1, k}). Graphs and Combinatorics, 21, 89-96. [Google Scholar] [CrossRef] 
[8] Ho, P.T. (2007) The Crossing Number of the Circular Graph C(3k + 1;{1, k}). Discrete Mathematics, 307, 2771-2774. [Google Scholar] [CrossRef] 
[9] McQillan, D. and Richter, R.B. (1992) On the Crossing Numbers of Certain Generalized Petersen Graphs. Discrete Mathematics, 104, 311-320. [Google Scholar] [CrossRef] 
[10] Richter, R.B. and Salazar, G. (2002) The Crossing Number of P(N, 3). Graphs and Combinatorics, 18, 381-394. [Google Scholar] [CrossRef] 
[11] Székely, L.A. (2004) A Successful Concept for Measuring Non-Planarity of Graphs: The Crossing Number. Discrete Mathematics, 276, 331-352. [Google Scholar] [CrossRef] 
[12] Salazar, G. (2005) On the Crossing Numbers of Loop Net-works and Generalized Petersen Garaphs. Discrete Mathematics, 302, 243-253. [Google Scholar] [CrossRef] 
[13] Lu, W., Li, F., Ren, H., et al. (2023) On the Crossing Points of Circulant Graphs C(9, 3). International Journal of Mathematics and Systems Science, 6, 206-211.

为你推荐