[K1,1,2,2×Sn]的交叉数

doi:10.3778/j.issn.1002-8331.1705-0081

计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (14): 52-55.DOI: 10.3778/j.issn.1002-8331.1705-0081

[K1,1,2,2×Sn]的交叉数

苏振华

怀化学院数学系，湖南怀化 418008

出版日期:2018-07-15 发布日期:2018-08-06

Crossing number of K1,1,2,2×Sn

SU Zhenhua

Department of Mathematics, Huaihua University, Huaihua, Hunan 418008, China

Online:2018-07-15 Published:2018-08-06

摘要/Abstract

摘要： 确定图的交叉数是一个NP-完全问题。目前关于完全多部图与星图的积图交叉数的结果较少。根据完全多部图[K1,1,2,2]的结构特点，引入收缩的方法，得到了积图[K1,1,2,2×Sn]交叉数与完全多部图[K1,1,2,2,n]交叉数的关系为[cr(K1,1,2,2×Sn)=cr(K1,1,2,2,n)+4n]。

关键词: 交叉数, 笛卡尔积, 星图, 完全多部图

Abstract: Determining the crossing number of an arbitrary graph is NP-complete problem. There are known few results on the crossing numbers of Cartesian product for complete multipartite graphs with stars. This paper uses the structure characteristics of [K1,1,2,2] and the contraction operations, obtains the relationship of crossing numbers of [K1,1,2,2×Sn] with [K1,1,2,2,n] is [cr(K1,1,2,2×Sn)=cr(K1,1,2,2,n)+4n].

Key words: crossing number, Cartesian product, star, complete multipartite graph

苏振华. [K1,1,2,2×Sn]的交叉数[J]. 计算机工程与应用, 2018, 54(14): 52-55.

SU Zhenhua. Crossing number of K1,1,2,2×Sn[J]. Computer Engineering and Applications, 2018, 54(14): 52-55.

[1]	丁成，翁理国，夏旻，崔逸尘，钱俊豪，刘佳. 多注意力机制网络卫星图像分割算法[J]. 计算机工程与应用, 2021, 57(2): 223-229.
[2]	苏振华. 联图[K1,1,3∨Cn]的交叉数[J]. 计算机工程与应用, 2018, 54(9): 57-61.
[3]	王雪飞. 卫星图像的村落民居Lebesgue测度η值研究[J]. 计算机工程与应用, 2015, 51(10): 195-199.
[4]	岳为君1，黄元秋1，欧阳章东2. 联图[W4+Cn]的交叉数[J]. 计算机工程与应用, 2014, 50(18): 79-84.
[5]	卢鹏，王锡淮，肖健梅. 连续属性决策表离散化的图论方法[J]. 计算机工程与应用, 2012, 48(6): 13-16.
[6]	张帆，熊炎，方明科. 布尔函数零化子次数的一个错误证明的更正[J]. 计算机工程与应用, 2012, 48(6): 84-85.
[7]	杨文华，李生刚. 区间值模糊图的分解性质[J]. 计算机工程与应用, 2012, 48(31): 25-29.
[8]	郭涛，么炜，苑迎春. 利用遗传算法改进DAG绘制的方法[J]. 计算机工程与应用, 2011, 47(8): 172-174.

[K1,1,2,2×Sn]的交叉数

Crossing number of K1,1,2,2×Sn

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics