EN|RU

Том 18, номер 6, 2011 г., Стр. 33-60

УДК 519.174
Константинова Е. В., Медведев А. Н.
Циклы длины девять в pancake графе

Аннотация:
В Pancake графе $P_n$, $n\ge3$, являющемся графом Кэли на симметрической группе перестановок с порождающим множеством всех префикс-реверсалов, существуют все циклы длины $l$, где $6\le l\le n!$. Полная характеризация циклов длины шесть и семь, представленных в виде произведения порождающих элементов, получена недавно. В настоящей статье продолжены исследования циклов нечётной длины в данном графе. Для циклов длины девять получено их полное описание в виде 10 канонических форм и показано, что через любую вершину графа $P_n$, $n\ge4$, проходит $\frac{8n^3-45n^2+61n-12}2$ различных циклов длины девять. В целом, в графе имеется $O(n!\,n^3)$ циклов длины девять.
Ил. 5, табл. 1, библиогр. 10.

Ключевые слова: граф Кэли, симметрическая группа, Pancake граф, вложение циклов.

Константинова Елена Валентиновна 1,2
Медведев Алексей Николаевич 2

1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: e_konsta@math.nsc.ru, an_medvedev@yahoo.com

Статья поступила 25 апреля 2011 г.
Исправленный вариант — 13 июля 2011 г.

 © Институт математики им. С. Л. Соболева, 2015