|
Zapiski Nauchnykh Seminarov POMI, 2019, Volume 488, Pages 119–142
(Mi znsl6914)
|
|
|
|
This article is cited in 1 scientific paper (total 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.
Received: 18.11.2019
Citation:
E. C. Krasko, I. N. Labutin, A. V. Omelchenko, “Enumeration of labelled and unlabelled Hamiltonian cycles in complete $k$-partite graphs”, Combinatorics and graph theory. Part XI, Zap. Nauchn. Sem. POMI, 488, POMI, St. Petersburg, 2019, 119–142
Linking options:
https://www.mathnet.ru/eng/znsl6914 https://www.mathnet.ru/eng/znsl/v488/p119
|
Statistics & downloads: |
Abstract page: | 91 | Full-text PDF : | 36 | References: | 25 |
|