Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
On the complexity of Cayley graphs on a dihedral group. / Hua, Bobo; Mednykh, A. D.; Mednykh, I. A. и др.
в: Discrete Mathematics, Том 349, № 1, 114662, 01.01.2026.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - On the complexity of Cayley graphs on a dihedral group
AU - Hua, Bobo
AU - Mednykh, A. D.
AU - Mednykh, I. A.
AU - Wang, Lili
N1 - The first author was supported by NSFC, no. 11831004 and Shanghai Science and Technology Program [Project No. 22JC1400100]. The second and the third authors were supported by the state contract of Sobolev Institute of Mathematics with the Ministry of Science and Higher Education of the Russian Federation (Project No. FWNF-2026-0026). The fourth author is supported by the NSFC (No. 12101125 and 12371052) and the Fujian Alliance of Mathematics (Project No. 2024SXLMMS01).
PY - 2026/1/1
Y1 - 2026/1/1
N2 - 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,(ab)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.
AB - 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,(ab)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.
KW - Cayley graph
KW - Chebyshev polynomial
KW - Dihedral group
KW - Spanning tree
UR - https://www.scopus.com/pages/publications/105009690193
UR - https://www.mendeley.com/catalogue/048e18f0-a4ba-3a97-a771-14aa8bd32dc6/
U2 - 10.1016/j.disc.2025.114662
DO - 10.1016/j.disc.2025.114662
M3 - Article
VL - 349
JO - Discrete Mathematics
JF - Discrete Mathematics
SN - 0012-365X
IS - 1
M1 - 114662
ER -
ID: 68675538