Bisection widths of transposition graphs
Ladislav Stacho, Imrich Vrt’o · 2002
We prove lower and upper bounds on bisection widths of the transposition graphs. This class of graphs contains several frequently studied interconnection networks including star graphs and hypercubes. In particular, we prove that the bisection width of the complete transposition graph is of order /spl Theta/(n.n!!) which solves the open problem (R) 3.356 of F.T. Leighton (1992) and determine nearly exact value of bisection width of the star graph. The results have applications to VLSI layouts, cutwidths and crossing numbers of transposition graphs. We also study bandwidths of transposition graphs.