"Записки научных семинаров ПОМИ"
Том 488, стр. 119-142
Перечисление помеченных и непомеченных гамильтоновых циклов в полных $k$-дольных графах
enter> Е. С. Краско, И. Н. Лабутин,
А. В. Омельченко
Национальный
исследовательский университет
``Высшая школа экономики''
ул. Союза Печатников, д.16,
С.-Петербург, 190008, Россия
krasko.evgeniy@gmail.ru
labutin.igorl@gmail.ru
avo.travel@gmail.com
- Аннотация:
Статья посвящена перечислению помеченных и непомеченных гамильтоновых циклов в полных $n$-дольных графах $K_{d,d,\ldots,d}$, в каждой доле которых содержится ровно $d$ вершин. В работе получены рекуррентные соотношения, позволяющие подсчитать точное количество $b_{n}^{(d)}$ таких графов для произвольных значений параметров $n$ и $d$.
Библ. -- 14 назв.
- Ключевые слова: гамильтоновы циклы; полный n-дольный граф; хордовая диаграмма; линейная диаграмма; перечисление помеченных и непомеченных объектов
[Hamiltonian cycles; Tur\'an graphs; complete $n$-partite graphs; chord diagrams; linear diagrams; labelled and unlabelled enumeration]
Полный текст(.pdf)