ASYMPTOTIC BEHAVIOR OF RESISTANCE DISTANCES IN CAYLEY GRAPHS
https://doi.org/10.29235/1561-8323-2018-62-2-140-146
Abstract
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.
About the Authors
M. M. Vaskouski
Belarusian State University
Belarus
Assosiate professor
Belarus
Assosiate professor
A. O. Zadorozhnyuk
Belarusian State University
Belarus
Student
Belarus
Student
References
1. Chandra 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/bf01270385
2. Ellens 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.024
3. Bapat 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-1003
4. Sauerwald T. Randomized Protocols for Information Dissemination. University of Padeborn, 2008.
5. Heydemann M.-C. Cayley graphs and interconnection networks. Graph Symmetry, 1997, pp. 167–224. DOI: 10.1007/978-94-015-8937-6_5
6. Suzuki 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.2600
7. Vaskouski 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.044
8. Krebs M., Shaneen A. Expander Families and Cayley Graphs. Oxford University Press, 2011. 283 p.
9. Benjamini 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-4
10. Gould R. Graph Theory. Dover, 2012.
11. Babai 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.103440
12. Lyons R., Peres Y. Probability on Trees and Networks. Cambridge University Press, 2016. 720 p.
13. 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.
14. Konstantinova E. Vertex reconstruction in Cayley graphs. Discrete Mathematics, 2009, vol. 309, no. 3, pp. 548–559. DOI: 10.1016/j.disc.2008.07.039
15. Gates 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
Review
Views: 921
Email this article 