Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949543 | Discrete Applied Mathematics | 2017 | 15 Pages |
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
Maksim Vaskouski, Anna Zadorozhnyuk,