English

运筹学学报 >

2022 , Vol. 26 >Issue 4: 98 - 106

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.04.008

交叉数为2的笛卡尔积图

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

收稿日期: 2019-09-06

  网络出版日期: 2022-11-28

基金资助

湖南省教育厅重点项目(No. 19A043), 湖南省社科基金教育学专项课题(No. JJ194000),湖南省重点实验室(No. 2019TP1011)

收起

Cartesian product graphs with crossing number two

Expand
  • 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 date: 2019-09-06

  Online published: 2022-11-28

Fold

摘要

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

关键词： 交叉数; 画法; 笛卡尔积图

本文引用格式

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

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 G1 and G2 for which the crossing number of G1□G2 is two if G1 is a cycle. This paper studies the necessary and sufficient conditions of G1 and G2 for which cr(G1□G2) = 2 if |V(G1)| > 3.

Key words： crossing number; drawing; Cartesian product graph

参考文献

[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 K5,n[J]. Journal of Combinatorial Theory, 1970, 9: 315-323.
[4] Richter R B, Širáň J. The crossing number of K3,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] 吕胜祥, 黄元秋. K2,4□Sn的交叉数[J]. 系统科学与数学, 2010, 30(7): 929-935.
[9] 马祖强, 蔡俊亮. W5□Sn的交叉数[J]. 应用数学学报2008, 31: 615-623.
[10] 欧阳章东, 黄元秋. Km-□Pn的交叉数[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 Cm and Pn[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 K1,3,n and K2,3,n[J]. Journal of Graph Theory, 1980, 10: 1-8.
[22] Klešč M. The crossing numbers of K2,3□Pn and K2,3□Sn[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.
Options
文章导航

/

〈 〉