Article ID Journal Published Year Pages File Type
4949543 Discrete Applied Mathematics 2017 15 Pages PDF
Abstract
The present paper is devoted to estimating effective resistances in large weighted undirected Cayley graph Cay(Sn,Tn) on symmetric group Sn. We obtain asymptotically exact bounds for minimal resistances in Cay(Sn,Tn). Maximal and average resistances in Cayley graphs on symmetric groups are given in terms of degree, girth and spectral gap. Sharp asymptotic bounds for maximal and average resistances are obtained for star and transposition Cayley graphs. Finally, we find improved estimates of effective resistances in bubble-sort Cayley graphs.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,