On the Crossing Points of Circulant Graphs C(9, 3)
Vol 6, Issue 2, 2023
VIEWS - 693 (Abstract) 50 (PDF)
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. D.J. Ma was proved that the crossing number of C(2m + 2, m) is m + 1[8]. Then such problem for C(n, 3) was further solved [7]. Pak Tung Ho and X. Lin obtained accurate values for the crossover numbers of C (3m, m) and C (3m + 1, m)[4][5]. In this paper, as a complement, we show that the edges from the principal cycle of C(9, 3) do not cross each other in an optimal drawing.
Keywords
Full Text:
PDFReferences
1. Bondy JA, Murty USR, Graph Theory with Applications, Macmilan Ltd. Press, New York (1976).
2. Garey MR, Johnson DS, Crossing number is NP-complete, Slam J. Alg. Disc.Math. 1 (1983), 312-316.
3. Hao RX, Liu YP, New upper bounds on crossing number of circular graph, OR Transactions 3 (1999), 1-6.
4. Pak Tung Ho, The crossing number of the circular graph C(3k + 1, k), Discrete Math. 307 (2007), 2771-2774.
5. Lin X, Yang Y, Lv J, Hao X, The crossing number of C(mk, k), Graphs Combin. 21 (2005), 89-96.
6. Lu JJ, Ren H, Ma DJ, On the crossing number of C(m, 3), J. Sys. Sci Math. Scis. 24(4) (2004), 504-512.
7. Lu JJ, Wu YR, Ren H, Crossing number of certain circular graphs, Journal of East China Normal University 2 (2005), 16-22.
8. Ma DJ, Ren H, Lu JJ, The crossing number of the circular graph C(2m + 2, m), Discrete Math. 304 (2005), 88-93.
9. McQillan D, Richter RB, On the crossing numbers of certain generalized Petersen graphs, Discrete Math. 104 (1992), 311-320.
10. Mohar B and Thomassen C, Graphs on Surfaces, Johns Hopkins Univ. Press, 2001.
11. Richter RB, Salazar G, The crossing number of P (N, 3), Graphs Combin. 18 (2002), 381-394.
12. Salazar G, On the crossing numbers of loop networks and generalized Petersen garaphs, Discrete Math. 302 (2005), 243-253.
13. Sz´ekely LA, A successful concept for measuring non-planarity of graphs: the crossing number, Discrete Math. 276 (2004), 331-352.
DOI: https://doi.org/10.24294/ijmss.v6i2.2481
Refbacks
- There are currently no refbacks.
![Creative Commons License](http://i.creativecommons.org/l/by-nc/4.0/88x31.png)
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
This site is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.