点击次数：

论文类型：期刊论文

发表时间：2008-03-01

发表刊物：UTILITAS MATHEMATICA

收录刊物：SCIE

卷号：75

页面范围：211-224

ISSN号：0315-3681

关键字：knodel graph; crossing number; interconnection networks.

摘要：Knodel graphs have been widely studied as interconnection networks, mainly because of their good properties in terms of broadcasting and gossiping. The crossing number of a network (graph) is closely related to the minimum layout area required for the implementation of a VLSI circuit for that network. Garey and Johnson have proved that the problem of determining the crossing number of an arbitrary graph is NP-complete (Crossing number is NP-complete, SIAM If. Alg. Disc. Meth. 4 (1983) 312-316). With this important application in mind, it makes most sense to analyze the crossing number of Knodel graphs. In this paper we study the crossing number of the Knodel graph and prove that cr(W3,8) = 0 cr(W3,10) = 1 and cr(W3,n) = [n/6] + (n. mod 6)/2 for even n >= 12.