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

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

Abstract

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

摘要： 确定图的交叉数是一个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]。

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

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

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

[1]	WEI Dingfeng, LI Liang, CHAI Jing. Social Recommendation Algorithm by Fusing Item Information [J]. Computer Engineering and Applications, 2021, 57(19): 198-204.
[2]	GU Junhua, CHEN Bo, WANG Rui, ZHANG Suqi. Social Recommendation Combined with Important Nodes Trust Propagation [J]. Computer Engineering and Applications, 2021, 57(17): 190-195.
[3]	HU Xuelin, Hasan·Wumaier. Review on Recommender Algorithms Based on Distributed Representation Technology [J]. Computer Engineering and Applications, 2020, 56(22): 13-24.
[4]	WANG Lei, SUN Lifan. Research on Path Planning Algorithm with Obligatory Node Constraint [J]. Computer Engineering and Applications, 2020, 56(21): 25-29.
[5]	LIU Changyong, WANG Yihuai, CAI Chuanghua, JIANG Jianwu. Anatomy of Real-Time Operating System mbedOS Startup Process [J]. Computer Engineering and Applications, 2020, 56(20): 46-51.
[6]	SU Zhenhua. Crossing numbers of join products of K1,1,3∨Cn [J]. Computer Engineering and Applications, 2018, 54(9): 57-61.
[7]	ZHAO Jiang, ZHANG Yan, MA Zewen, YE Zichao. Improvement and verification of A-star algorithm for AGV path planning [J]. Computer Engineering and Applications, 2018, 54(21): 217-223.
[8]	ZHU Yan1, YOU Xiaoming1, LIU Sheng2, YUAN Wanghuang1. Research for robot path planning problem based on improved Ant Colony System（ACS） algorithm [J]. Computer Engineering and Applications, 2018, 54(19): 129-134.
[9]	WENG Xiaolan1，2, WANG Zhijian1. Research process of collaborative filtering recommendation algorithm [J]. Computer Engineering and Applications, 2018, 54(1): 25-31.
[10]	XIE Linquan, LIANG Boqun. Collaborative filtering recommendation based on user characteristics classification and dynamic time [J]. Computer Engineering and Applications, 2017, 53(6): 80-84.
[11]	DUAN Dekun, FU Xiufen. Research on user cold start problem in hybrid collaborative filtering algorithm [J]. Computer Engineering and Applications, 2017, 53(21): 151-156.
[12]	PEI Wenjie, WANG Feng, TAN Yanghong, YIN Jian, JIANG Qinji. Multi-objective optimal strategy for units start-up during power system restoration based on bat algorithm [J]. Computer Engineering and Applications, 2017, 53(2): 225-230.
[13]	WAGN Lucai, CHEN Chaohua, WANG Tao, XIANG Wei. Design and realization of chromatography peak identification algorithm in water quality testing [J]. Computer Engineering and Applications, 2017, 53(11): 237-240.
[14]	ZHOU Houqing. Construction of hyperenergetic integral circulant graphs for network topology [J]. Computer Engineering and Applications, 2016, 52(9): 23-27.
[15]	CAO Mengyi, HUANG Sui, WANG Huijin, HE Jie, LONG Shun. Content-based approach to exercise route recommendation [J]. Computer Engineering and Applications, 2016, 52(9): 33-38.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics