Изопериметрический профиль и резистивные диаметры графов Кэли на симметрической группе с порождающими множествами Коксетера
https://doi.org/10.29235/1561-2430-2025-61-2-106-117
Об авторах
М. М. ВаськовскийБеларусь
Васьковский Максим Михайлович – доктор физико-математических наук, профессор, заведующий кафедрой ФМИС
пр. Независимости, 4, 220030, Минск
А. О. Задорожнюк
Беларусь
Задорожнюк Анна Олеговна – кандидат физико- математических наук, доцент кафедры ФМИС
пр. Независимости, 4, 220030, Минск
А. В. Гонимар
Беларусь
Гонимар Алексей Владимирович – студент
пр. Независимости, 4, 220030, Минск
Список литературы
1. Krebs M., Shaneen A. Expander Families and Cayley Graphs. Oxford University Press, 2011. 288 p.
2. Lyons R., Peres Y. Probability on Trees and Networks, Cambridge University Press, 2016. 699 p. http://doi.org/10.1017/9781316672815
3. Klartag B., Kozma G., Ralli P., Tetali P. Discrete curvature and abelian groups. Canadian Journal of Mathematics, 2016, vol. 6, no. 3, pp. 655–674. https://doi.org/10.4153/CJM-2015-046-8
4. Chung F. Four proofs for the cheeger inequality and graph partition algorithms. AMS/IP Studies in Advanced Mathematics, 2010, vol. 48, pp. 331–349. https://doi.org/10.1090/amsip/048/17
5. Ohring S. R., Sarkar F., Das S. K., Hohndel D. H. Cayley graph connected cycles: a new class of fixed-degree interconnection networks. Proceedings of HICSS’95. Wailea, 1995, pp. 479–488. https://doi.org/10.1109/HICSS.1995.375509
6. Akers S. B., Krishnamurthy B. A group-theoretic model for symmetric interconnection networks. IEEE Transactions on Computers, 1989, vol. 38, no. 4, pp. 555– 565. https://doi.org/10.1109/12.21148
7. Sauerwald T. Randomized Protocols for Information Dissemination. Padeborn, 2008. 150 p.
8. Heydemann M. C. Cayley graphs and interconnection networks. Graph Symmetry. NATO ASI Series. Dordrecht, Springer, 1997, vol. 497, pp. 167–224. https://doi.org/10.1007/978-94-015-8937-6_5
9. Luxburg U., Radl A., Hein M. Hitting and commute times in large random neighbourhood graphs. Journal of Machine Learning Research, 2014, vol. 15, no. 52, pp. 1751– 1798. https://dl.acm.org/doi/10.5555/2627435.2638591
10. Klein D. J., Randic M. Resistance distance. Journal of Mathematical Chemistry, 1993, vol. 12, no. 1, pp. 81–95. https://doi.org/10.1007/BF01164627
11. Seshu S., Reed M. B. Linear graphs and electrical networks. Addison-Wesley Publishing Company, 1961. 315 p.
12. Gvishiani A. D., Gurvich V. A. Metric and ultrametric spaces of resistances. Russian Mathematical Surveys, 1987, vol. 42, no. 6, pp. 235–236. https://doi.org/10.1070/rm1987v042n06abeh001494
13. Babai L., Szegedy M. Local expansion of symmetrical graphs. Combinatorics, Probability and Computing, 1992, vol. 1, no. 1, pp. 1–11. https://doi.org/10.1017/S0963548300000031
14. Alahmadi A., Alhazmi H., Ali S., Deza M., Sikiric M. D., Sole P. Hypercube emulation of interconnection networks topologies. Mathematical Methods in Applied Sciences, 2016, vol. 39, no. 16, pp. 4856–4865. https://doi.org/10.1002/mma.3820
15. Hart S. A note on the edges of the n-cube. Discrete Mathematics, 1976, vol. 14, no. 2, pp. 157–163. https://doi.org/10.1016/0012-365X(76)90058-3
16. Mohar B. Isoperimetric numbers of graphs. Journal of Combinatorial Theory, Series B, 1989, vol. 47, no. 3, pp. 274–291. https://doi.org/10.1016/0095-8956(89)90029-4
17. Bollobas B., Leader L. Edge-isoperimetric inequalities in the grid. Combinatorica, 1991, vol. 11, no. 4, pp. 299–314. https://doi.org/10.1007/BF01275667
18. Siconolfi V. Ricci curvature, graphs and eigenvalues. Linear Algebra and its Applications, 2021, vol. 620, pp. 242–267. https://doi.org/10.1016/j.laa.2021.02.026
19. Konstantinova E. Vertex reconstruction in Cayley graphs. Discrete Mathematics, 2009, vol. 309, no. 3, pp. 548–559. https://doi.org/10.1016/j.disc.2008.07.039
20. Vaskouski M. M., Zadorozhnyuk A. O. Asymptotic behavior of resistance distances in Cayley graphs. Doklady Natsional’noi akademii nauk Belarusi = Doklady of the National Academy of Sciences of Belarus, 2018, vol. 62, no. 2, pp. 140–146 (in Russian). https://doi.org/10.29235/1561-8323-2018-62-2-140-146
21. Godsil C., Royle G. Algebraic Graph Theory. Springer, 2001. 443 p. https://doi.org/10.1007/978-1-4613-0163-9
22. Gould R. Graph Theory. Dover Publications, Inc., 2012. 350 p.
23. Atzmon N., Ellis D., Kogan D. An isoperimetric inequality for conjugation invariant sets in the symmetric group. Israel Journal of Mathematics, 2016, vol. 212, no. 1, pp. 139–162. https://doi.org/10.1007/s11856-016-1296-7
24. Benjamini I., Kozma G. A resistance bound via an isoperimetric inequality. Combinatorica, 2005, vol. 25, no. 6, pp. 645–650. https://doi.org/10.1007/s00493-005-0040-4
25. Friedman J. On Cayley graphs on the symmetric group generated by transpositions. Combinatorica, 2000, vol. 20, no. 4, pp. 505–519. https://doi.org/10.1007/s004930070004
26. Kalpakis K., Yesha, Y. On the bisection width of the transposition network. Networks, 1997, vol. 29, no. 1, pp. 69–76. https://doi.org/10.1002/(sici)1097-0037(199701)29:1<69::aid-net7>3.0.co;2-a
27. 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. https://doi.org/10.1007/BF01270385
28. Gurvich V. Metric and ultrametric spaces of resistances. Discrete Applied Mathematics, 2010, vol. 158, no. 14, pp. 1496–1505. https://doi.org/10.1016/j.dam.2010.05.007
29. Vaskouski M., Zadorozhnyuk A. Resistance distances in Cayley graphs on symmetric group. Discrete Applied Mathematics, 2017, vol. 227, pp. 121–135. https:/doi.org/10.1016/j.dam.2017.04.044
30. Kaneko K., Suzuki Y. Node-to-node internally disjoint paths problem in bubble-sort graphs. 10th IEEE Pacific Rim International Symposium on Dependable Computing, 2004. Proceedings, pp. 173–182. https://doi.org/10.1109/PRDC.2004.1276568