关于交叉数为1的联图  

On the Join Graphs with Crossing Number One

作　　者：王晶 欧阳章东[2] 黄元秋[3] WANG JING OUYANG ZHANGDONG HUANG YUANQIU(College of Mathematics and Computer Science, Changsha University, Changsha 410003, China Department of Mathematics, Hunan First Normal University, Changsha 410205, China College of Mathematics and Computer Science, Hunan Normal University, Changsha 410081, China)

机构地区：[1]长沙学院计算机工程与应用数学学院,长沙410003 [2]湖南第一师范学院数学系,长沙410205 [3]湖南师范大学数学与计算机科学学院,长沙410081

出　　处：《应用数学学报》2017年第5期727-733,共7页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(No.11371133);湖南省自然科学基金(No.14JJ3138);湖南省教育厅优秀青年项目(No.16B028)资助项目

摘　　要：确定图的交叉数是NP-完全问题.Kuratowski定理刻画了平面图的特征,而结合图的交叉数这一参数来研究非平面图的特征,目前相关结果甚少.本文从联图着手,研究当G_1VG_2的交叉数为1时,刻画出因子图G_1和G_2须满足的充要条件.Determining the crossing number of a given graph is NP-complete. It is well known that Kuratowski＇s Theorem characterizes the graph whose crossing number is 0. For non-planar graph G with crossing number k （k ≥ 1）, there are few results concerning on characterizing the structure of G. This paper is dedicated to characterize graphs G1 and G2 for which the crossing number of their join G1 V G2 is one.

关 键 词：交叉数 画法 联图 

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