АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ РЕЗИСТОРНЫХ РАССТОЯНИЙ В ГРАФАХ КЭЛИ
https://doi.org/10.29235/1561-8323-2018-62-2-140-146
Анатацыя
В настоящей работе доказаны асимптотически точные оценки для резисторных расстояний в некоторых семействах графов Кэли при условии, что функция роста является как минимум субэкспоненциальной, а диаметр либо обратная величина к спектральному пробелу полиномиальны по степени графа.
Аб аўтарах
М. Васьковский
Белорусский государственный университет, Минск
Беларусь
Беларусь
А. Задорожнюк
Белорусский государственный университет, Минск
Беларусь
Беларусь
Спіс літаратуры
1. The electrical resistance of a graph captures its commute and cover times / A. K. Chandra [et al.] // Comput. Complex. – 1996. – Vol. 6, N 4. – P. 312–340. DOI: 10.1007/bf01270385
2. Effective graph resistance / W. Ellens [et al.] // Linear Algebra and its Applications. – 2011. – Vol. 435, N 10. – P. 2491–2506. DOI: 10.1016/j.laa.2011.02.024
3. Bapat, R. B. A simple method for computing resistance distance / R. B. Bapat, I. Gutmana, W. Xiao // Z. Naturforsch. – 2003. – Vol. 58, N 9–10. – P. 494–498. DOI: 10.1515/zna-2003-9-1003
4. Sauerwald, T. Randomized Protocols for Information Dissemination. / T. Sauerwald. – University of Padeborn, 2008.
5. Heydemann, M.-C. Cayley graphs and interconnection networks / M.-C. Heydemann // Graph Symmetry. – 1997. – P. 167–224. DOI: 10.1007/978-94-015-8937-6_5
6. Suzuki, Y. Node-disjoint paths algorithm in a transposition graph / Y. Suzuki, K. Kaneko, M. Nakamori // IEICE Trans. Inf. Syst. – 2006. – Vol. E89-D, N 10. – P. 2600–2605. DOI: 10.1093/ietisy/e89-d.10.2600
7. Vaskouski, M. Resistance distances in Cayley graphs on symmetric groups / M. Vaskouski, A. Zadorozhnyuk // Discrete Applied Mathematics. – 2017. – Vol. 227. – P. 121–135. DOI: 10.1016/j.dam.2017.04.044
8. Krebs, M. Expander Families and Cayley Graphs / M. Krebs, A. Shaneen. – Oxford University Press, 2011. – 283 p.
9. Benjamini, I. A resistance bound via an isoperimetric inequality / I. Benjamini, G. Kozma // Combinatorica. – 2005. – Vol. 25, N 6. – P. 645–650. DOI: 10.1007/s00493-005-0040-4
10. Gould, R. Graph Theory / R. Gould. – Dover, 2012.
11. Babai, L. Local expansion of vertex-transitive graphs and random generation in finite groups / L. Babai // Proceedings of the twenty-third annual ACM symposium on Theory of computing. – 1991. – P. 164–174. DOI: 10.1145/103418.103440
12. Lyons, R. Probability on Trees and Networks / R. Lyons, Y. Peres. – Cambridge University Press, 2016. – 720 p.
13. Chung, F. The spectral gap of graphs arising from substring reversals / F. Chung, J. Tobin // The Electronic Journal of Combinatorics. – 2017. – Vol. 23, N 3. – P. 1–18.
14. Konstantinova, E. Vertex reconstruction in Cayley graphs / E. Konstantinova // Discrete Mathematics. – 2009. – Vol. 309, N 3. – P. 548–559. DOI: 10.1016/j.disc.2008.07.039
15. Gates, W. H. Bounds for sorting by prefix reversal / W. H. Gates, C. H. Papadimitriou // Discrete Mathematics. – 1979. – Vol. 27, N 1. – P. 47–57. DOI: 10.1016/0012-365x(79)90068-2
##reviewer.review.form##
Праглядаў: 920
Паслаць артыкул па эл. пошце 