On the bisection width of the transposition network

DOI10.1002/(SICI)1097-0037(199701)29:1%3C69::AID-NET7%3E3.0.CO;2-AMaRDI QIDQ4345575zbMATH OpenOpenAlexFDO

Authors Konstantinos Kalpakis, Yaacov Yesha

Publication date 23 July 1997

Full work available at URL https://doi.org/10.1002/(sici)1097-0037(199701)29:1%3C69::aid-net7%3E3.0.co;2-a

zbMATH Keywords

adjacency matrixbisection widthCayley grapheigenvaluesymmetric grouptransposition network

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Recommendations

• Bisection width of transposition graphs
• On the bisection width and expansion of butterfly networks
• scientific article; zbMATH DE number 1092191
• An observation on the bisectional interconnection networks
• The restricted connectivity of complete-transposition networks
• A better upper bound on the bisection width of de Bruijn networks (extended abstract)
• The bisection width of grid graphs
• Laying out the interconnection network of the transpose bijection
• A lower bound on the transposition diameter

Cited in

(14)

• Bisection width of transposition graphs
• Spectrum of the transposition graph
• On the second largest eigenvalue of some Cayley graphs of the symmetric group
• Eigenvalues of Cayley graphs
• Extremal even-cycle-free subgraphs of the complete transposition graphs
• Resistance distances in Cayley graphs on symmetric groups
• Disjoint Hamilton cycles in transposition graphs
• The property of edge-disjoint Hamiltonian cycles in transposition networks and hypercube-like networks
• Distinct eigenvalues of the Transposition graph
• Resistance diameters and critical probabilities of Cayley graphs on irreducible complex reflection groups
• A hook formula for eigenvalues of k-point fixing graphs
• Isoperimetric profile and resistance diameters of Cayley graphs on symmetric groups with Coxeter generating sets
• Quadratic interval of eigenvalues of the transposition graph
• On the partitions associated with the smallest eigenvalues of certain Cayley graphs on symmetric group generated by cycles

This page was built for publication: On the bisection width of the transposition network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4345575)