An Upper Bound for the Crossing Number of Locally Twisted Cubes

Wang, Haoli; Xu, Xirong; Yang, Yuansheng; Liu, Bao; Zheng, Wenping; Wang, Guoging

Abstract

References

Ars Combinatoria

Volume 131
Pages: 87-106

Research article

An Upper Bound for the Crossing Number of Locally Twisted Cubes

^¹, ^², ^², ^², ^³, ^⁴

¹College of Computer and Information Engineering Tianjin Normal University, Tianjin, 300387, P. R. China

²Department of Computer Science Dalian University of Technology, Dalian, 116024, P. R. China

³Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Shanxi University, Taiyuan, 030006, P. R. China

⁴Department of Mathematics Tianjin Polytechnic University, Tianjin, 300387, P. R. China

Published: 31/01/2017

Copyright Link
License

Abstract

The crossing number of a graph $G$ is the minimum number of pairwise intersections of edges in a drawing of $G$ . The $n$ -dimensional locally twisted cubes $L T Q_{n}$ , proposed by X.F. Yang, D.J. Evans and G.M. Megson, is an important interconnection network with good topological properties and applications. In this paper, we mainly obtain an upper bound on the crossing number of $L T Q_{n}$ , no more than $\frac{265}{6} 4^{n - 4} - (n^{2} + \frac{15 + (- 1)^{n - 1}}{6} 2^{n - 3}$ .

Contents

Ars Combinatoria

An Upper Bound for the Crossing Number of Locally Twisted Cubes

Abstract

Information

Guidelines

CP Initiatives

Follow CP