Том 17, номер 5, 2010 г., Стр. 46-55
УДК 519.174
Константинова Е. В., Медведев А. Н.
Циклы длины семь в Pancake графе
Аннотация:
Ранее в pancake графе$P_n$ ,$n\geq3$ , являющемся графом Кэли на симметрической группе перестановок с порождающим множеством всех префикс-реверсалов, доказано существование циклов длины$l$ ,$6\leq l\leq n!$ . В настоящей статье даётся характеризация циклов длины семь, представленных в виде последовательности префикс-реверсалов. Доказано, что через любую вершину графа$P_n$ ,$n\geq4$ , проходит$7(n-3)$ циклов длины семь, а всего в графе имеется$n!(n-3)$ различных циклов длины семь.
Ил. 1, табл. 1, библиогр. 7.
Ключевые слова: pancake граф, граф Кэли, симметрическая группа, вложение циклов.
Константинова Елена Валентиновна 1,2
Медведев Алексей Николаевич 2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2.
Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: e_konsta@math.nsc.ru, an_medvedev@yahoo.com
Статья поступила 3 февраля 2010 г.
Исправленный вариант — 1 апреля 2010 г.
