Standard

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.

Результаты исследований: Научные публикации в периодических изданияхстатьяРецензирование

Harvard

APA

Vancouver

Hua B, Mednykh AD, Mednykh IA, Wang L. On the complexity of Cayley graphs on a dihedral group. Discrete Mathematics. 2026 янв. 1;349(1):114662. doi: 10.1016/j.disc.2025.114662

Author

Hua, Bobo ; Mednykh, A. D. ; Mednykh, I. A. и др. / On the complexity of Cayley graphs on a dihedral group. в: Discrete Mathematics. 2026 ; Том 349, № 1.

BibTeX

@article{f671ae6de6b64b6599bd88f88764398f,
title = "On the complexity of Cayley graphs on a dihedral group",
abstract = "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.",
keywords = "Cayley graph, Chebyshev polynomial, Dihedral group, Spanning tree",
author = "Bobo Hua and Mednykh, {A. D.} and Mednykh, {I. A.} and Lili Wang",
note = "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).",
year = "2026",
month = jan,
day = "1",
doi = "10.1016/j.disc.2025.114662",
language = "English",
volume = "349",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier Science Publishing Company, Inc.",
number = "1",

}

RIS

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