Hits:

Indexed by:期刊论文

Date of Publication:2008-03-01

Journal:UTILITAS MATHEMATICA

Included Journals:SCIE

Volume:75

Page Number:211-224

ISSN No.:0315-3681

Key Words:knodel graph; crossing number; interconnection networks.

Abstract: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.