| 一个六阶图与星图的笛卡儿积的交叉数 |
| |
| 引用本文： | 李波,张莉茜,黄元秋.一个六阶图与星图的笛卡儿积的交叉数[J].湖南文理学院学报(自然科学版),2008,20(2):6-11. |
| |
| 作者姓名： | 李波 张莉茜 黄元秋 |
| |
| 作者单位： | 湖南师范大学,数学与计算机科学学院,湖南,长沙,410081;湖南师范大学,数学与计算机科学学院,湖南,长沙,410081;湖南师范大学,数学与计算机科学学院,湖南,长沙,410081 |
| |
| 基金项目： | 国家自然科学基金
,
教育部跨世纪优秀人才培养计划 |
| |
| 摘 要： | 图的交叉数已被证明是一个NP-完全问题, 由于其难度, 要知道图的确切交叉数是非常困难的. 到目前为止,只知道少数图的交叉数, 其中大部分是特殊图的笛卡儿积图的交叉数, 比如路, 圈以及星图与点数较"少"的图的笛卡儿积交叉数. 在这些基础上, 应用数学归纳法, 把相关结果拓展到1个6-阶图G,并确定它与星的笛卡儿积交叉G×Sn Z(6,n) 3n/2] .
|
| 关 键 词： | 图 画法 交叉数 星 笛卡儿积 |
The crossing number of cartesian product of star with a 6-vertex graph |
| |
| LI Bo,ZHANG Li-xi,HUANG Yuan-qiu.The crossing number of cartesian product of star with a 6-vertex graph[J].Journal of Hunan University of Arts and Science:Natural Science Edition,2008,20(2):6-11. |
| |
| Authors: | LI Bo ZHANG Li-xi HUANG Yuan-qiu |
| |
| Institution: | LI Bo,ZHANG Li-xi,HUANG Yuan-qiu (Department of Mathematics,Hunan Normal University,Changsha,Hunan,410081) |
| |
| Abstract: | Computing the crossing number of a given graph has been proved to be NP-complete. It is very difficult to determine the exact crossing number of a given graph for its complicity. The crossing numbers of few families of graphs are known. So far, most of which are Cartesian Products of special graphs, such as Cartesian Products of paths, cycles or stars with small vertex graphs. On these basis, by using the induction method, this paper extends these results to a special 6-vertex graph G and then determines th... |
| |
| Keywords: | graph drawing crossing number star cartesian |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
