danДоклады Национальной академии наук БеларусиDoklady of the National Academy of Sciences of Belarus1561-83232524-2431The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-8323-2018-62-2-140-146dan-500Research ArticleМАТЕМАТИКАMATHEMATICSАСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ РЕЗИСТОРНЫХ РАССТОЯНИЙ В ГРАФАХ КЭЛИASYMPTOTIC BEHAVIOR OF RESISTANCE DISTANCES IN CAYLEY GRAPHSВаськовскийМ. М.VaskouskiM. M.

доцент

Assosiate professor

vaskovskii@bsu.byЗадорожнюкА. О.ZadorozhnyukA. O.

студент

Student

a_zadorozhnyuk@mail.ruБелорусский государственный университет, МинскBelarusian State University201820052018622140146Copyright © Васьковский М.М., Задорожнюк А.О., 20182018Васьковский М.М., Задорожнюк А.О.Vaskouski M.M., Zadorozhnyuk A.O.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.belnauka.by/jour/article/view/500

В настоящей работе доказаны асимптотически точные оценки для резисторных расстояний в некоторых семействах графов Кэли при условии, что функция роста является как минимум субэкспоненциальной, а диаметр либо обратная величина к спектральному пробелу полиномиальны по степени графа.

 

 

 

 

In the present paper, we prove asymptotically exact bounds for resistance distances in families of Cayley graphs that either have a girth of more than 4 or are free of subgraphs K2,t, assuming that the growth function is at least subexponential, and either the diameter or the inverse value of the spectral gap are polynomial with respect to degrees of a graph.

граф Кэлирезисторное расстояниеспектральный пробелизопериметрическая постояннаяCayley graphsresistance distancespectral gapisoperimetric constantReferencesThe 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/bf01270385Chandra A. K., Raghavan P., Ruzzo W. L., Smolensky R., Tiwari P. The electrical resistance of a graph captures its commute and cover times. Computational Complexity, 1996, vol. 6, no. 4, pp. 312–340. DOI: 10.1007/bf01270385Effective 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.024Ellens W., Spieksma F. M., van Mieghem P., Jamakovic A., Kooij R. E. Effective graph resistance. Linear Algebra and its Applications, 2011, vol. 435, no. 10, pp. 2491–2506. DOI: 10.1016/j.laa.2011.02.024Bapat, 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-1003Bapat R. B., Gutmana I., Xiao W. A simple method for computing resistance distance. Zeitschrift für Naturforschung A, 2003, vol. 58, no. 9–10, pp. 494–498. DOI: 10.1515/zna-2003-9-1003Sauerwald, T. Randomized Protocols for Information Dissemination. / T. Sauerwald. – University of Padeborn, 2008.Sauerwald T. Randomized Protocols for Information Dissemination. University of Padeborn, 2008.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_5Heydemann M.-C. Cayley graphs and interconnection networks. Graph Symmetry, 1997, pp. 167–224. DOI: 10.1007/978-94-015-8937-6_5Suzuki, 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.2600Suzuki Y., Kaneko K., Nakamori M. Node-disjoint paths algorithm in a transposition graph. IEICE Transactions on Information and Systems, 2006, vol. E89-D, no. 10, pp. 2600–2605. DOI: 10.1093/ietisy/e89-d.10.2600Vaskouski, 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.044Vaskouski M., Zadorozhnyuk A. Resistance distances in Cayley graphs on symmetric groups. Discrete Applied Mathematics, 2017, vol. 227, pp. 121–135. DOI: 10.1016/j.dam.2017.04.044Krebs, M. Expander Families and Cayley Graphs / M. Krebs, A. Shaneen. – Oxford University Press, 2011. – 283 p.Krebs M., Shaneen A. Expander Families and Cayley Graphs. Oxford University Press, 2011. 283 p.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-4Benjamini I., Kozma G. A resistance bound via an isoperimetric inequality. Combinatorica, 2005, vol. 25, no. 6, pp. 645–650. DOI: 10.1007/s00493-005-0040-4Gould, R. Graph Theory / R. Gould. – Dover, 2012.Gould R. Graph Theory. Dover, 2012.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.103440Babai L. Local expansion of vertex-transitive graphs and random generation in finite groups. Proceedings of the twenty-third annual ACM symposium on Theory of computing, 1991, pp. 164–174. DOI: 10.1145/103418.103440Lyons, R. Probability on Trees and Networks / R. Lyons, Y. Peres. – Cambridge University Press, 2016. – 720 p.Lyons R., Peres Y. Probability on Trees and Networks. Cambridge University Press, 2016. 720 p.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.Chung F., Tobin J. The spectral gap of graphs arising from substring reversals. The Electronic Journal of Combinatorics, 2017, vol. 23, no. 3, pp. 1–18.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.039Konstantinova E. Vertex reconstruction in Cayley graphs. Discrete Mathematics, 2009, vol. 309, no. 3, pp. 548–559. DOI: 10.1016/j.disc.2008.07.039Gates, 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-2Gates W. H., Papadimitriou C. H. Bounds for sorting by prefix reversal. Discrete Mathematics, 1979, vol. 27, no. 1, pp. 47–57. DOI: 10.1016/0012-365x(79)90068-2

The authors declare that there are no conflicts of interest present.