Hits:

Indexed by:期刊论文

Date of Publication:2018-10-01

Journal:DISCRETE APPLIED MATHEMATICS

Included Journals:SCIE

Volume:247

Page Number:407-418

ISSN No.:0166-218X

Key Words:Drawing; Crossing number; Locally twisted cube; Interconnection network

Abstract:The crossing number of a graph G is the minimum number of pairwise intersections of edges in a drawing of G. Motivated by the recent work (Faria et al., 2008) which solves the upper bound conjecture on the crossing number of n-dimensional hypercube proposed by Erdos and Guy, we consider the crossing number of locally twisted cubes LTQ(n), which is one of important variation of the hypercube Q(n). In this paper, we obtain the upper bound of the crossing number of LTQ(n) as follows.
   cr(LTQ(n)) <= 87/512 4(n) - 4n(2) - 15 + (-1)(n-1) /32 2(n).
   (C) 2018 Elsevier B.V. All rights reserved.