交叉数为2的笛卡尔积图  

Cartesian product graphs with crossing number two

作　　者：王晶 张作政[1] WANG Jing;ZHANG Zuozheng(College of Mathematics and Computer Science,Changsha University,Changsha 410003,Hunan,China;Hunan Province Key Laboratory of Industrial Internet Technology and Security,Changsha University,Changsha 410003,Hunan,China)

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

出　　处：《运筹学学报》2022年第4期98-106,共9页Operations Research Transactions

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

摘　　要：图G的交叉数,记作cr(G),是把G画在平面上的所有画法中边与边产生交叉的最小数目,它是拓扑图论中的一个热点问题。Kle?c和Petrillová刻画了当G为圈且cr(GG)-2时,因子图G和G满足的充要条件。在此基础上,本文研究当|V(G)|≥3且cr(GG)=2时,G和G应满足的充要条件。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.Klesc and Petrillova characterized graphs Gand Gfor which the crossing number of G□Gis two if Gis a cycle.This paper studies the necessary and sufficient conditions of Gand Gfor which cr(G□G)=2 if|V(G)I≥3.

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

分 类 号：O157.5[理学—数学]