| 一个五阶图与星图的笛卡尔积交叉数 |
| |
| 引用本文： | 何小年,段凤华.一个五阶图与星图的笛卡尔积交叉数[J].河南师范大学学报(自然科学版),2009,37(1). |
| |
| 作者姓名： | 何小年 段凤华 |
| |
| 作者单位： | 1. 湖南涉外经济学院,电气与信息工程学部,长沙,410000
2. 中南大学,交通运输工程学院,长沙,410000 |
| |
| 基金项目： | 国家自然科学基金，湖南省教育厅资助项目 |
| |
| 摘 要： | 确定图的交叉数被证明是一个NP-完全问题,因为其难度,能够确定交叉数的具体图类非常少.M.Klecˇ等人确定了一些关于阶数不超过5的图与路、星和圈的笛卡尔积图的交叉数.本文扩展了他们的结果,确定了1个5阶图与星图的笛卡尔积图的交叉数.
|
| 关 键 词： | 图 画法 交叉数 星图 笛卡尔积 |
Crossing Numbers of Cartesian Products of Stars with 5-vertex Graph |
| |
| HE Xiao-nian,DUAN Feng-hua.Crossing Numbers of Cartesian Products of Stars with 5-vertex Graph[J].Journal of Henan Normal University(Natural Science),2009,37(1). |
| |
| Authors: | HE Xiao-nian DUAN Feng-hua |
| |
| Institution: | 1.School of Electric Information Engineering;Hunan Internationl Economics University;Changsha 410000;China;2.School of Traffic and Transport Engineering;Central South University;China |
| |
| Abstract: | 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.Marián Klec 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. |
| |
| Keywords: | graph drawing crossing number star cartesian product |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
