摘要
确定图的交叉数被证明是一个NP-完全问题,因为其难度,能够确定交叉数的具体图类非常少.M.Klecˇ等人确定了一些关于阶数不超过5的图与路、星和圈的笛卡尔积图的交叉数.本文扩展了他们的结果,确定了1个5阶图与星图的笛卡尔积图的交叉数.
Garey and Johxon have proved that the problem to determine the crossing number of graphs is NP-complete, Because of its difficulty, presently the crossing number of some classes of special graphs is known. Marian Klesc has computed the crossing numbers of some the Cartesian products of 5-vertex graphs with paths, cycles and stars. In this paper these results are extended,and determine that the crossing number of Cartesian product of four specific 5-vertice graphs with star.
出处
《河南师范大学学报(自然科学版)》
CAS
CSCD
北大核心
2009年第1期17-19,共3页
Journal of Henan Normal University(Natural Science Edition)
基金
国家自然科学基金(10771062)
湖南省教育厅资助项目(08C518)
关键词
图
画法
交叉数
星图
笛卡尔积
graph
drawing
crossing number
star
cartesian product