交叉数为2的笛卡尔积图

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

运筹学学报 ›› 2022, Vol. 26 ›› Issue (4): 98-106.doi: 10.15960/j.cnki.issn.1007-6093.2022.04.008

交叉数为2的笛卡尔积图

王晶^1,2, 张作政^1*

1. 长沙学院计算机工程与应用数学学院, 湖南长沙 410003;
2. 长沙学院工业互联网技术与安全湖南省重点实验室, 湖南长沙 410003

收稿日期:2019-09-06 发布日期:2022-11-28
通讯作者: 张作政 E-mail:zuozhengzhang@ccsu.edu.cn
基金资助:
湖南省教育厅重点项目(No. 19A043), 湖南省社科基金教育学专项课题(No. JJ194000),湖南省重点实验室(No. 2019TP1011)

Cartesian product graphs with crossing number two

WANG Jing^1,2, ZHANG Zuozheng^1*

1. College of Mathematics and Computer Science, Changsha University, Changsha 410003, Hunan, China;
2. Hunan Province Key Laboratory of Industrial Internet Technology and Security, Changsha University, Changsha 410003, Hunan, China

Received:2019-09-06 Published:2022-11-28

摘要/Abstract

摘要： 图G的交叉数, 记作cr(G), 是把G画在平面上的所有画法中边与边产生交叉的最小数目, 它是拓扑图论中的一个热点问题。Klešč和 Petrillová刻画了当G₁为圈且cr(G₁□G₂)=2时, 因子图G₁和G₂满足的充要条件。在此基础上, 本文研究当|V(G₁)|≥3且cr(G₁□G₂)=2时, G₁和G₂应满足的充要条件。

关键词: 交叉数, 画法, 笛卡尔积图

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

中图分类号:

O157.5

王晶, 张作政. 交叉数为2的笛卡尔积图[J]. 运筹学学报, 2022, 26(4): 98-106.

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

参考文献

[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.

交叉数为2的笛卡尔积图

Cartesian product graphs with crossing number two

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价

[1]	苏振华. 六阶图C_6+3K_2与P_n, C_n的联图交叉数[J]. 运筹学学报, 2017, 21(3): 23-34.
[2]	周志东, 李龙 . 一个特殊6点图Q与nK_{1}, P_{n}及C_{n}的联图交叉数[J]. 运筹学学报, 2016, 20(4): 115-126.
[3]	欧阳章东, 黄元秋. 完全二部图K_{3,3}与星S_n的积图的交叉数[J]. 运筹学学报, 2014, 18(2): 69-76.
[4]	周志东，王晶. W₆*S_n的交叉数[J]. 运筹学学报, 2013, 17(2): 10-18.
[5]	袁梓瀚黄元秋. 泊松图P(4,1)与路Pn的笛卡尔积的交叉数[J]. 运筹学学报, 2011, 15(3): 95-106.