五阶图与星图的笛卡尔积交叉数

• 作 者: 何小年 黄元秋
• 机 构: 湖南涉外经济学院电气与信息工程学部,湖南师范大学数学与计算机科学学院
• 出 处: 哈尔滨工业大学学报
• 发表日期: 2009年3期
• 关键词: 图 画法 交叉数 星图 笛卡尔积 同胚 graph drawing crossing number star cartesian product h
• 基金项目: 国家自然科学基金资助项目（10271045）,湖南省教育厅科学研究资助项目（08C518）.

Garey和Johxon已经证明了确定图的交叉数是一个NP-完全问题，因为其难度，能够确定交叉数的图类非常少，关于阶数不超过5的图与路和圈的笛卡尔积图的交叉数大部分已经知道，但是，五阶图与星图笛卡尔积图：的交叉数的已知结果还很少．本文扩展了他们的结果，确定了4个5阶图与星图的笛卡尔积图的交叉数．