Том 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 г.
Литература
[1] Константинова Е. В., Медведев А. Н. Циклы длины семь в Pancake графе // Дискрет. анализ и исслед. операций. — 2010. — T. 17, № 5. — С. 46–55.
[2] Asai S., Kounoike Y., Shinano Y., Kaneko K. Computing the diameter of 17-pancake graph using a PC cluster // Euro–Par 2006 Parallel Processing. Proc. 12th Int. Euro–Par Conf. (Dresden, Germany, August 28–September 1, 2006). — Berlin; Heidelberg: Springer-Verl., 2006. — P. 1114–1124. (Lect. Notes Comput. Sci.; Vol. 4128.)
[3] Cibulka J. On average and highest number of flips in pancake sorting // Theor. Comput. Sci. — 2011. — Vol. 412. — P. 822–834.
[4] Dweighter H. E 2569 in elementary problems and solutions // Amer. Math. Monthly. — 1975. — Vol. 82, N 1. — P. 1010.
[5] Gates W. H., Papadimitriou C. H. Bounds for sorting by prefix-reversal // Discrete Math. — 1979. — Vol. 27. — P. 47–57.
[6] Hyedari M. H., Sudborough I. H. On the diameter of the pancake network // J. Algorithms. — 1997. — Vol. 25, N. 1. — P. 67–94.
[7] Kanevsky A., Feng C. On the embedding of cycles in pancake graphs // Parall. Comput. — 1995. — Vol. 21. — P. 923–936.
[8] Ke Qiu. Optimal broadcasting algorithms for multiple messages on the star and pancake graphs using minimum dominating sets // Congr. Numerantium. — 2006. — Vol. 181. — P. 33–39.
[9] Sheu J. J., Tan J. J. M., Chu K. T. Cycle embedding in pancake interconnection networks // Proc. 23rd Workshop Comb. Math. Comput. Theory (Taiwan, 2006). — Changhua, Taiwan: Da-Yeh Univ. Press, 2006. — P. 85–92.
[10] Zaks S. A new algorithm for generation of permutations// BIT. — 1984. — Vol. 24. — P. 196–204.
