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

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

doi:10.24294/ijmss.v6i2.2481

Home - IJMSS - Volume 6 - Issue 2

Submit to IJMSS

Journal Browser

Volume | Year

Issue

• Current lssue

View All

News and Announcements

Jul 6, 2022

The International Mathematical Union Five Awards ceremony was held at Aalto University
Mar 12, 2022

European Mathematical Society 30th Anniversary Celebration

View All

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

Weihua Lu

Fang Li

Han Ren

Junjie Lu

Dengju Ma

International Journal of Mathematics and Systems Science 2023, 6(2); https://doi.org/10.24294/ijmss.v6i2.2481

Submitted：21 Jul 2023

Accepted：21 Jul 2023

Published：28 Jul 2023

Download PDF(403.27KB)

XML

Abstract

It is well known that determining the exact values of crossing number for circulant graphs is very diﬃcult. 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

References

Bondy JA, Murty USR, Graph Theory with Applications, Macmilan Ltd. Press, New York (1976).

Garey MR, Johnson DS, Crossing number is NP-complete, Slam J. Alg. Disc.Math. 1 (1983), 312-316.

Hao RX, Liu YP, New upper bounds on crossing number of circular graph, OR Transactions 3 (1999), 1-6.

Pak Tung Ho, The crossing number of the circular graph C(3k + 1, k), Discrete Math. 307 (2007), 2771-2774.

Lin X, Yang Y, Lv J, Hao X, The crossing number of C(mk, k), Graphs Combin. 21 (2005), 89-96.

Lu JJ, Ren H, Ma DJ, On the crossing number of C(m, 3), J. Sys. Sci Math. Scis. 24(4) (2004), 504-512.

Lu JJ, Wu YR, Ren H, Crossing number of certain circular graphs, Journal of East China Normal University 2 (2005), 16-22.

Ma DJ, Ren H, Lu JJ, The crossing number of the circular graph C(2m + 2, m), Discrete Math. 304 (2005), 88-93.

McQillan D, Richter RB, On the crossing numbers of certain generalized Petersen graphs, Discrete Math. 104 (1992), 311-320.

Mohar B and Thomassen C, Graphs on Surfaces, Johns Hopkins Univ. Press, 2001.

Richter RB, Salazar G, The crossing number of P (N, 3), Graphs Combin. 18 (2002), 381-394.

Salazar G, On the crossing numbers of loop networks and generalized Petersen garaphs, Discrete Math. 302 (2005), 243-253.

Sz´ekely LA, A successful concept for measuring non-planarity of graphs: the crossing number, Discrete Math. 276 (2004), 331-352.

Previous
article in this issue

Next
article in this issue