6-阶图与路的笛卡儿积交叉数

• 作者: 王晶 黄元秋
• 来源期刊: 吉首大学学报（自然科学版）
• 学科: 数学
• 关键词: 图 画法 交叉数 路 笛卡儿积
• 年，卷（期）: 2005,（2）
• 所属期刊栏目: NSFC成果
• 页码范围: 9-13
• 页数: 5页
• 分类号: O157.5
• 字数: 1629字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-2985.2005.02.003

摘要

图的交叉数是指把图画在平面上边与边产生的交叉数目的最小值.图的交叉数只在好画法中得到,好画法是指满足边自身不交叉,相关联的边不交叉,任意两条交叉的边至多交叉一次的画法.图的交叉数已被证明是一个NP-完全问题,由于其难度,要知道图的确切交叉数是非常困难的.到目前为止,只知道少数图的交叉数,其中大部分是特殊图的笛卡儿积图的交叉数,比如路,圈以及星图与点数较"少"的图的笛卡儿积交叉数.在这些基础上,应用数学归纳法,把相关结果拓展到4个6-阶图与长为的路的笛卡儿积交叉数.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄元秋	湖南师范大学数学与计算机科学学院	111	474	13.0	17.0
2	王晶	湖南师范大学数学与计算机科学学院	10	97	6.0	9.0