Перечисление помеченных и непомеченных гамильтоновых циклов в полных k-дольных графах $K_{d,d,\ldots,d}$

Задача перечисления гамильтоновых циклов в тех или иных семействах графов является одной из наиболее сложных задач перечислительной комбинаторики. Помимо некоторых тривиальных примеров (таких, например, как гамильтоновы циклы в полных графах), в литературе практически отсутствуют содержательные результаты, связанные с получением точного количества гамильтоновых циклов в графах. В силу очевидной сложности подобного рода задач усилия специалистов в теории графов сконцентрированы в основном на получении верхних или нижних оценок. Еще меньше результатов имеется в области перечисления непомеченных гамильтоновых циклов.
Представленная работа посвящена перечислению помеченных и непомеченных гамильтоновых циклов в полных k-дольных графах $K_{d,d,\ldots,d}$. В основе решения лежит подход, основанный на переходе к так называемым обобщенным хордовым, а затем и обобщенным линейным диаграммам. Получены явные рекуррентные соотношения, которые позволяют подсчитать количество гамильтоновых циклов для произвольных значений параметра $d$ как в помеченном, так и в непомеченном случаях.