Дискретные расслоения Зейферта над графами и их сложность

Обложка

Цитировать

Полный текст

Аннотация

В настоящей работе мы рассматриваем бесконечное семейство графов Hn = Hn(G1, G2, ..., Gm), представляющих из себя дискретные расслоения Зейферта над заданным графом H на m вершинах с особыми слоями G1, G2, ..., Gm. Каждый слой Gi = Cn(si,1, si,2, ..., si,ki) такого расслоения является циркулянтным графом на n вершинах со скачками si,1, si,2, ..., si,ki. Семей-ство дискретных расслоений Зейферта достаточно обширно. Оно включает обобщённые графы Петерсена, I-графы, Y-графы, H-графы, сандвичи циркулянтных графов, дискретные торы и др. В работе получены формулы для числа порождающих деревьев t(n) графа Hn в терминах полиномов Чебышева, изучены аналитические и арифметические свойства этой функции и найдена её асимптотика при n → ∞.

Об авторах

Йонг Су Квон

Йоннамский университет

Email: smedn@mail.ru
Республика Корея, Кёнсан-Пукто, Кёнсан, Даёханг-ро 280

А. Д. Медных

Институт математики имени С.Л. Соболева Сибирского отделения Российской академии наук; Новосибирский национальный исследовательский государственный университет

Автор, ответственный за переписку.
Email: smedn@mail.ru
Россия, 630090, г. Новосибирск, пр-т акад. Коптюга, 4; 630090, г. Новосибирск, ул. Пирогова, 1

И. А. Медных

Институт математики имени С.Л. Соболева Сибирского отделения Российской академии наук; Новосибирский национальный исследовательский государственный университет

Email: smedn@mail.ru
Россия, 630090, г. Новосибирск, пр-т акад. Коптюга, 4; 630090, г. Новосибирск, ул. Пирогова, 1

Список литературы

  1. Boesch F.T., Prodinger H. // Graphs and Combin. 1986. V. 2. 1. P. 191-200.
  2. Golin M.J., Xuerong Yong, Yuanping Zhang // Discrete Math. 2010. V. 310. P. 792-803.
  3. Sun W., Wang S., Zhang J. // J. Appl. Anal. Comput. 2016. V. 6. 1. P. 65-75.
  4. Wu F.Y. // J. Phys. A: Math. Gen. 1977. V. 10. P. L113-115.
  5. Shrock R., Wu F.Y. // J. Phys. A: Math. Gen. 2000. V. 33. P. 3881-3902.
  6. Guttmann A.J., Rogers M.D. // J. Phys. A: Math. Theor. 2012. V. 45. 49. 494001.
  7. Louis J. //Bull. Aust. Math. Soc. 2015. V. 92, 3. P. 365-373.
  8. Abrosimov N.V., Baigonakova G.A., Mednykh I.A. // Sib. Electronic Math. Rep. 2018. V. 15. P. 1145-1157.
  9. Kwon Y.S., Mednykh A.D., Mednykh I.A. // Linear Algebra Appl. 2017, V. 529, P. 355-373.
  10. Медных А.Д., Медных И.А. // ДАН. 2018. Т. 479. № 4. С. 363-367.
  11. Mednykh I.A. // Ars Math. Contemp. 2018. V. 15. P. 467-485.
  12. Horton J.D., Bouwer I.Z. // J. Combin. Theory. Ser. B. 1991. V. 53. P. 114-129.
  13. Kwon Y.S., Mednykh A.D., Mednykh I.A. // arXiv: 1811.03801v1 [math.CO] 09 Nov 2018.
  14. Lorenzini D. // J. Combin. Theory Ser. B. 2008. V. 98. 6. P. 1271-1300.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2019