Preview

Доклады Национальной академии наук Беларуси

Расширенный поиск

АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ РЕЗИСТОРНЫХ РАССТОЯНИЙ В ГРАФАХ КЭЛИ

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


Просмотров: 355


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1561-8323 (Print)
ISSN 2524-2431 (Online)