On the Crossing Points of Circulant Graphs C(9, 3)

Weihua Lu, Fang Li, Han Ren, Junjie Lu, Dengju Ma

Article ID: 2481
Vol 6, Issue 2, 2023

VIEWS - 686 (Abstract) 42 (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


Crossing Number; Crossing Point; Circulant Graphs

Full Text:

PDF


References


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
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Creative Commons License

This site is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.