Abstract: В настоящем докладе мы рассматриваем спектр и сложность беско- нечного семейства графов Кэли $$\mathcal{D}_{n} = Cay(\mathbb{D}_{n},b^{β_1},b^{β_2},...,b^{β_s}, ab^{γ_1},ab^{γ_2},...,ab^{γ_t}),$$ соответствующих группам диэдра $\mathbb{D}_n = ⟨a, b|a^2 = 1, b^n = 1, (a b)^2 = 1⟩$ порядка $2n.$ Получена замкнутая формула для числа τ(n) остовных деревьев в $\mathbb{D}_n$ в терминах полиномов Чебышева, исследованы некоторые арифметические свойства этой функции и найдена ее асимптотика при n → ∞. Также показано, что производящая функция $F(x)=\sum_{n=1}^{∞} τ(n)x^{n}$ является рациональной функцией с целыми коэффициентами.

Cite: Медных А.Д.
О сложности графa Кэли на диэдральной группе
Комбинаторно-вычислительные методы алгебры и логики 15-19 июл. 2024