Индекс Кирхгофа для циркулянтных графов

Индекс Кирхгофа для циркулянтных графов

Медных А. Д., Медных И. А.
Сибирский математический журнал, 65, 6, 1191-1206 (2024)
Скачать статью

УДК 517.545+517.962.2+519.173 
DOI: 10.33048/smzh.2024.65.610

Аннотация:

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

Литература:
  1. Mohar B. The Laplacian spectrum of graphs // Graph theory, combinatorics, and applications: Alavi Y., Chartrand G., Oellermann O. R., Schwenk A. J. (eds.). New York: Wiley, 1991. V. 2. P. 871–898. 
     
  2. Klein D. J., Randić M. Resistance distance // J. Math. Chem. 1993. V. 12. P. 81–95.
     
  3. Wiener H. Structural determination of paraffin boiling points // J. Am. Chem. Soc. 1947. V. 69, N 1. P. 17–20.
     
  4. Gutman I., Mohar B. The quasi-Wiener and the Kirchhoff indices coincide // J. Chem. Inf. Comput. Sci. 1996. V. 36. P. 982–985.
     
  5. Zhu H. Y., Klein D. J., Lukovits I. Extensions of the Wiener number // J. Chem. Inf. Model. 1996. V. 36, N 3. P. 420–428.
     
  6. Lukovits I., Nikolić S., Trinajstić N. Resistance distance in regular graphs // Int. J. Quantum Chem. 1999. V. 71. P. 217–225.
     
  7. Palacios J. L. Closed-form formulas for Kirchhoff index // Int. J. Quantum Chem. 2001. V. 81. P. 135–140.
     
  8. Xiao W., Gutman I. Resistance distance and Laplacian spectrum // Theor. Chem. Acc. 2003. V. 110. P. 284–289. 
     
  9. Zhang H., Yang Y. Resistance distance and Kirchhoff index in circulant graphs // Int. J. Quantum Chem. 2007. V. 107, N 2. P. 330–339.
     
  10. Luzhen Y. On the Kirchhoff index of some toroidal lattices // Linear and Multilinear Algebra. 2011. V. 59, N 6. P. 645–650.
     
  11. Cinkir Z. Effective resistances and Kirchhoff index of ladder graphs // J. Math. Chem. 2016. V. 54, N 4. P. 955–966.
     
  12. Somodi M. On the Ihara zeta function and resistance distance-based indices // Linear Algebra Appl. 2017. V. 513. P. 201–209.
     
  13. Mitsuhashi H., Morita H., Sato I. The weighted Kirchhoff index of a graph // Linear Algebra Appl. 2018. V. 547. P. 1–18.
     
  14. Kagan M., Mata B. A physics perspective on the resistance distance for graphs // Math. Comput. Sci. 2019. V. 13. P. 105–115.
     
  15. Baigonakova G. A., Mednykh A. D. Elementary formulas for Kirchhoff index of Möbius ladder and prism graphs // Sib. Electron. Mat. Rep. 2019. V. 16. P. 1654–1661.
     
  16. Медных А. Д., Медных И. А. Индекс Кирхгофа для циркулянтных графов и его асимптотика // Докл. АН. 2020. Т. 494, № 1. С. 43–47.
     
  17. Adám A. Research problems 2–10 // J. Combin. Theory. 1967. V. 2. P. 393.
     
  18. Conder M., Grande R. On embeddings of circulant graphs // Electron. J. Combinatorics. 2015. V. 22, N 2. #P2.28.
     
  19. Muzychuk M. A solution of the isomorphism problem for circulant graphs // Proc. London Math. Soc. (3). 2004. V. 88. P. 1–41.
     
  20. Evdokimov S., Ponomarenko I. Recognition and verification of an isomorphism of circulant graphs in polynomial time // St. Petersburg Math. J. 2004. V. 15. P. 813–835.
     
  21. Davis P. J. Circulant matrices. Providence, RI: AMS Chelsea Publ., 1994. V. 338.
     
  22. Mednykh A. D., Mednykh I. A. The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic // Discrete Math. 2019. V. 342. P. 1772–1781.
     
  23. Cinkir Z. Effective resistances and Kirchhoff index of prism graphs. 2017. 9 p. Cornell Univ. arXiv:1704.03429v1 [math.CO].

Работа выполнена в рамках государственного задания ИМ СО РАН, проект FWNF-2022- 0005.

Медных Александр Дмитриевич (ORCID 0000-0003-3084-1225
  1. Институт математики им. С. Л. Соболева СО РАН, 
    пр. Академика Коптюга, 4, Новосибирск 630090
  2. Новосибирский государственный университет, 
    ул. Пирогова, 1, Новосибирск 630090

E-mail: smedn@mail.ru

Медных Илья Александрович (ORCID 0000-0001-7682-3917)
  1. Институт математики им. С. Л. Соболева СО РАН, 
    пр. Академика Коптюга, 4, Новосибирск 630090
  2. Новосибирский государственный университет, 
    ул. Пирогова, 1, Новосибирск 630090

E-mail: ilyamednykh@mail.ru

Статья поступила 28 августа 2024 г.
После доработки — 28 августа 2024 г.
Принята к публикации 23 октября 2024 г.