交叉数为2的笛卡尔积图

doi:10.15960/j.cnki.issn.1007-6093.2022.04.008

Abstract

Abstract: The crossing number of a graph G, denoted by cr(G), is the minimum number of edge crossings in all drawings of G. The research on the crossing number of a graph is an active problem in topology graph theory. Klešč and Petrillová characterized graphs G₁ and G₂ for which the crossing number of G₁□G₂ is two if G₁ is a cycle. This paper studies the necessary and sufficient conditions of G₁ and G₂ for which cr(G₁□G₂) = 2 if |V(G₁)| > 3.

Key words: crossing number, drawing, Cartesian product graph

CLC Number:

O157.5

WANG Jing, ZHANG Zuozheng. Cartesian product graphs with crossing number two[J]. Operations Research Transactions, 2022, 26(4): 98-106.

References

[1] Bondy J A, Murty U S R. em Graph Theory[M]. New York: Springer, 2008.
[2] Garey M R, Johnson D S. Crossing number is NP-complete[J]. SIAM Journal on Algebraic Discrete Methods, 1983, 4: 312-316.
[3] Kleitman D J. The crossing number of K_5,n[J]. Journal of Combinatorial Theory, 1970, 9: 315-323.
[4] Richter R B, Širáň J. The crossing number of K_3,n in a surface[J]. Journal of Graph Theory, 1996, 21: 51-54.
[5] Yang Y S, Lin X H, Lu J, et al. The crossing number of C(n;{1,3})[J]. Discrete Mathematics, 2004, 289: 107-118.
[6] Ma D J, Ren H, Lu J. The crossing number of the circular graph C(2m+2,m)[J]. Discrete Mathematics, 2005, 304: 88-93.
[7] 卢俊杰, 任韩, 马登举. C(m,3)的交叉数[J]. 系统科学与数学, 2004, 24: 504-512.
[8] 吕胜祥, 黄元秋. K_2,4□S_n的交叉数[J]. 系统科学与数学, 2010, 30(7): 929-935.
[9] 马祖强, 蔡俊亮. W₅□S_n的交叉数[J]. 应用数学学报2008, 31: 615-623.
[10] 欧阳章东, 黄元秋. K_m^-□P_n的交叉数[J]. 数学学报, 2016, 59(3): 405-410.
[11] Klešč M. The crossing numbers of Cartesian products of paths with 5-vertex graphs[J]. Discrete Mathematics, 2001, 233: 353-359.
[12] Bokal D. On the crossing numbers of Cartesian products with paths[J]. Journal of Combinatorial Theory Series B, 2007, 97: 381-384.
[13] Alfaro C A, Arroyo A, Derňár M, et al. The crossing number of the cone of a graph[J]. SIAM Journal on Discrete Mathematics, 2018, 32: 2080-2093.
[14] Behzad M, Mahmoodian S E. On topological invariants of the product of graphs[J]. Canadian Mathematical Bulletin, 1969, 12: 157-166.
[15] Klešč M, Petrillová J. On Cartesian products with small crossing numbers[J]. Carpathian Journal of Mathematics, 2012, 28: 67-75.
[16] 王晶, 欧阳章东, 黄元秋. 交叉数为2且因子图为路的笛卡尔积图[J]. 应用数学学报, 2020, 43(1): 119-128.
[17] Bokal D. On the crossing numbers of Cartesian products with trees[J]. Journal of Graph Theory, 2007, 56: 287-300.
[18] Tang L, Wang J, Huang Y Q. The crossing number of the join of C_m and P_n[J]. International Journal of Mathmatical Combinatorics, 2007, 1: 110-116.
[19] Harborth H. Parity of numbers of crossings for complete n-partite graphs[J]. Mathematica Slovaca, 1976, 26: 77-95.
[20] Klešč M, Petrillová J. On the optimal drawings of products of paths with graphs[J]. Acta Electrotechnica et Informatica, 2013, 13: 56-61.
[21] Asano K. The crossing number of K_1,3,n and K_2,3,n[J]. Journal of Graph Theory, 1980, 10: 1-8.
[22] Klešč M. The crossing numbers of K_2,3□P_n and K_2,3□S_n[J]. Tatra Mountains Mathematical Publications, 1996, 9: 51-56.
[23] Klešč M. The crossing numbers of products of paths and stars with 4-vertex graphs[J]. Journal of Graph Theory, 1994, 18: 605-614.

Cartesian product graphs with crossing number two

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 5

Recommended Articles

Metrics

Comments

[1]	SU Zhenhua. The crossing number of the join product of C_6+3K_2 with P_n and C_n [J]. Operations Research Transactions, 2017, 21(3): 23-34.
[2]	ZHOU Zhidong, LI Long. On the crossing numbers of join of the special graph on six vertices with nK_1, P_n or C_n [J]. Operations Research Transactions, 2016, 20(4): 115-126.
[3]	OUYANG Zhangdong, HUANG Yuanqiu. On the crossing number of products of K_3,3 with S_n [J]. Operations Research Transactions, 2014, 18(2): 69-76.
[4]	ZHOU Zhidong,WANG Jing. On the crossing numbers of W₆*S_n [J]. Operations Research Transactions, 2013, 17(2): 10-18.
[5]	YUAN Zi-Han- Huang-Yuan-Qiu. The crossing Number of Petersen graph P(4,1) with paths Pn [J]. Operations Research Transactions, 2011, 15(3): 95-106.