Premium
On the bisection width of the transposition network
Author(s) -
Kalpakis Konstantinos,
Yesha Yaacov
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199701)29:1<69::aid-net7>3.0.co;2-a
Subject(s) - transposition (logic) , bisection , computer science , combinatorics , mathematics , algorithm , artificial intelligence , geometry
The transposition network T n of order n ! is the Cayley graph of the symmetric group S n with generators the set of all transpositions in S n . Finding the bisection width of the transposition network is an open question posed by F. T. Leighton. We resolve this question for n even, by showing that the bisection width of the transposition network T n is equal to nn !/4. When n ≥ 2 is odd, we show that the bisection width of the transposition network T n is (1 + o (1)) nn !/4. In doing so, we determine the second smallest eigenvalue of the adjacency matrix of T n . Further, given a Cayley graph of a finite group G , with m conjugacy classes and with a set of generators closed under taking conjugates and not containing the identity of G , we show how to construct an m × m integer matrix Q , from the conjugacy classes of G , such that the set of eigenvalues of Q is equal to the set of eigenvalues of the adjacency matrix A of the given Cayley graph. Hence, when the order of G is large compared to the number of its conjugacy classes, a faster method for computing the eigenvalues of A is provided. © 1997 John Wiley & Sons, Inc.