On the complexity of Cayley graphs on a dihedral group | Sciact - Система учета научной деятельности ИМ СО РАН

On the complexity of Cayley graphs on a dihedral group Научная публикация

Журнал

Discrete Mathematics
ISSN: 0012-365X , E-ISSN: 1872-681X

Вых. Данные

Год: 2026, Том: 349, Номер: 1, Номер статьи : 114662, Страниц : 11 DOI: 10.1016/j.disc.2025.114662

Ключевые слова

Spanning tree, Cayley graph, Dihedral group, Chebyshev polynomial

Авторы

Hua Bobo ¹ , Mednykh A.D. ^2,3 , Mednykh I.A. ^2,3 , Wang Lili ⁴

Организации

1	School of Mathematical Sciences, LMNS, Fudan University
2	Sobolev Institute of Mathematics
3	Novosibirsk State University
4	School of Mathematics and Statistics, Key Laboratory of Analytical Mathematics and Applications (Ministry of Education), Fujian Key Laboratory of Analytical Mathematics and Applications (FJKLAMA), Fujian Normal University

Информация о финансировании (1)

Министерство науки и высшего образования РФ

FWNF-2026-0026

In this paper, we investigate the complexity of an infinite family of Cayley graphs Dn = Cay(Dn, b±β1 , b±β2 ,..., b±βs ,abγ1 ,abγ2 ,...,abγt) on the dihedral group Dn = a, b|a2 = 1, bn = 1, (a b)2 = 1 of order 2n. We obtain a closed formula for the number τ (n) of spanning trees in Dn in terms of Chebyshev polynomials, investigate some arithmetical properties of this function, and find its asymptotics as n → ∞. Moreover, we show that the generating function F (x) = ∞ n=1 τ (n)xn is a rational function with integer coefficients

Hua B. , Mednykh A.D. , Mednykh I.A. , Wang L.
On the complexity of Cayley graphs on a dihedral group
Discrete Mathematics. 2026. V.349. N1. 114662 :1-11. DOI: 10.1016/j.disc.2025.114662 WOS Scopus OpenAlex

Поступила в редакцию:	29 дек. 2023 г.
Принята к публикации:	21 июн. 2025 г.
Опубликована online:	7 июл. 2025 г.
Опубликована в печати:	1 янв. 2026 г.

Web of science:	WOS:001529807400005
Scopus:	2-s2.0-105009690193
OpenAlex:	W4412092386

Пока нет цитирований