RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2019 Volume 488, Pages 119–142 (Mi znsl6914)

This article is cited in 1 paper

Enumeration of labelled and unlabelled Hamiltonian cycles in complete $k$-partite graphs

E. C. Krasko, I. N. Labutin, A. V. Omelchenko

National Research University "Higher School of Economics", St. Petersburg Branch

Abstract: We enumerate labelled and unlabelled Hamiltonian cycles in complete $n$-partite graphs $K_{d,d,\ldots,d}$ having exactly $d$ vertices in each part (in other words, Turán graphs $T(nd, n))$. We obtain recurrence relations that allow us to find the exact values $b_{n}^{(d)}$ of such cycles for arbitrary $n$ and $d$.

Key words and phrases: Hamiltonian cycles, Turán graphs, complete $n$-partite graphs, chord diagrams, linear diagrams, labelled and unlabelled enumeration.

UDC: 519.173.2+519.175.3

Received: 18.11.2019



© Steklov Math. Inst. of RAS, 2024