Граф Науру

В теории графов граф Науру — это симметричный двудольный кубический граф с 24 вершинами и 36 рёбрами. Граф был назван Дэвидом Эпштейном по аналогии с двенадцатилучевой звездой на флаге Науру.[1]

Граф Науру
Вершин 24
Рёбер 36
Радиус 4
Диаметр 4
Обхват 6
Автоморфизмы 144 (S4×S3)
Хроматическое число 2
Хроматический индекс 3
Свойства

кубический
симметричный
гамильтонов
двудольный
граф Кэли


целый
 Медиафайлы на Викискладе

Хроматическое число графа равно 2, хроматический индекс равен 3, диаметр — 4, радиус — 4, а обхват равен 6[2]. Граф является вершинно 3-связным и рёберно 3-связным.

Наименьшие кубические графы с числом пересечений 1-8 известны (последовательность A110507 в OEIS). Наименьший граф с 8 пересечениями — это граф Науру. Существует 5 неизоморфных кубических графов с 24 вершинами и числом пересечений 8[3]. Один из них — граф МакГи, известный также как (3-7)-клетка.[4]

Построение

Граф Науру является гамильтоновым и может быть описан с помощью LCF-нотации : [5, −9, 7, −7, 9, −5]4.[1]

Граф Науру можно также построить как обобщённый граф Петерсена G(12, 5), образованный вершинами двенадцатиугольника, где рёбра соединяют вершины в 12-лучевую звезду путём соединения вершин с шагом 5.

Также возможно построение на основе комбинаторики. Возьмём три различных объекта и положим в четыре неразличимых ящика, не более одного объекта в ящик. Существует 24 способа размещения объектов, что соответствует 24 вершинам графа. Если есть возможность перейти от одного размещения к другому путём перемещения ровно одного предмета в пустой ящик, две вершины соединяем ребром. Результирующий граф переходов от размещения к размещению является графом Науру.

Алгебраические свойства

Группа автоморфизмов графа Науру является группой порядка 144.[5]. Группа изоморфна прямому произведению симметрических групп S4 и S3 и действует транзитивно на вершинах, на рёбрах и дугах графа. Таким образом, граф Науру является симметричным (хотя и не дистанционно-транзитивным). Граф имеет автоморфизмы, которые переводят любую вершину в любую другую и любое ребро в любое другое. Согласно списку Фостера граф Науру является единственным кубическим симметричным графом с 24 вершинами[2].

Обобщённый граф Петерсена G(n, k) является вершинно-транзитивным в том и только в том случае, когда n = 10 и k =2 или если k2 ≡ ±1 (mod n) и является рёберно-транзитивным только в следующих случаях: (n, k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5)[6]. Таким образом, граф Науру является одним из семи симметричных обобщённых графов Петерсена. Среди этих семи графов кубический граф , граф Петерсена , Граф Мёбиуса — Кантора , граф додекаэдра и граф Дезарга .

Граф Науру является графом Кэли группы S4, симметрической группы перестановок четырёх элементов, образованной перестановками первого элемента с тремя другими: (1 2), (1 3) и (1 4).

Характеристический многочлен матрицы графа Науру равен

откуда следует, что граф является целым — графом, спектр которого состоит только из целых чисел.

Вложение в тор.
Тор образуется, топологически, путём склеивания противоположных рёбер правильного шестиугольника.
Обобщённый граф Петерсена.
цвета и перестановки показывают, что граф является графом Кэли группы S4.
Матрица смежности.
Каждое ребро представлено двумя элементами одного цвета, находящимися симметрично относительно диагонали.

Топологические свойства
Симметричное вложение графа Науру в поверхность рода 4 с шестью двенадцатиугольными гранями.

Граф Науру имеет два различных вложения как обобщённый правильный многогранник, при которых топологические поверхности разделены на рёбра, вершины и грани таким образом, что существует симметрия, переводящая любой флаг (инцидентная тройка из вершины, ребра и грани) в любой другой флаг[7].

Одно из этих двух вложений образует тор, так что граф Науру является тороидальным графом — он состоит из 12 шестиугольных граней вместе с 24 вершинами и 36 гранями графами Науру. Двойственный граф этого вложения является симметричным 6-регулярным графом с 12 вершинами и 36 рёбрами.

Другое симметричное вложение графа Науру имеет шесть двенадцатиугольных граней и образует поверхность рода 4. Его двойственный граф не является простым графом, поскольку каждая грань имеет три общих ребра с четырьмя другими гранями, а является мультиграфом. Этот двойственный граф можно образовать из графа правильного октаэдра путём замены каждого ребра тремя параллельными рёбрами.

Множество граней любого из этих двух вложений является множеством многоугольников Петри другого вложения.

Геометрические свойства
Граф Науру является графом единичных расстояний [8].

Как и все обобщённые графы Петерсена, граф Науру можно представить в виде точек плоскости таким образом, что смежные вершины находятся на расстоянии единица. Таким образом, он является графом единичных расстояний[8]. Этот граф и призма являются единственными обобщёнными графами Петерсена G(n,p), которые невозможно представить таким образом, что симметрии рисунка образуют циклическую группу порядка n. Взамен его представление в виде графа имеет в качестве группы симметрий диэдрическую группу Dih6.

История

Первым, кто написал о графе Науру, был Фостер (Foster), указав граф в списке всех кубических симметричных графов [9]. Полный список кубических симметричных графов назван теперь его именем (Список Фостера) и в этом списке графу Науру присвоен номер F24A, но не присвоено какое-либо имя[10]. В 1950 Коксетер упомянул граф во второй раз, дав гамильтоново представление для иллюстрации статьи и описав граф как граф Леви проективной конфигурации, открытой Цахариасом[11][12].

В 2003 Эд Пегг (Ed Pegg Jr.) написал в своей статье на сайте Математической ассоциации Америки, что F24A заслуживает имя, но не предложил какое-либо [13]. Наконец, в 2007, Дэвид Эпштейн использовал название граф Науру, поскольку флаг республики Науру содержит 12-лучевую звезду, аналогичную той, что возникает при построении графа как обобщённого графа Петерсена.[1]

Примечания
  1. David Eppstein, The many faces of the Nauru graph Архивировано 21 июля 2011 года. on LiveJournal, 2007.
  2. Conder, Dobcsányi, 2002, с. 40, 41-63.
  3. Pegg, Exoo, 2009.
  4. Weisstein, Eric W. Graph Crossing Number (англ.) на сайте Wolfram MathWorld.
  5. Royle, G. F024A data Архивная копия от 6 марта 2011 на Wayback Machine
  6. Frucht, Graver, Watkins, 1971, с. 211–218.
  7. McMullen, 1992, с. 285–289.
  8. Žitnik, Horvat, Pisanski, 2010.
  9. Foster, 1932, с. 309–317.
  10. Bouwer, Chernoff, Monson, Star, 1988.
  11. Coxeter, 1950, с. 413–455.
  12. Zacharias, 1941, с. 147–170.
  13. Pegg, 2003.

Литература
  • M. Conder, P. Dobcsányi. Trivalent Symmetric Graphs Up to 768 Vertices. // J. Combin. Math. Combin. Comput.. — 2002.
  • E. T. Pegg, G. Exoo. Crossing number graphs // Mathematica Journal. — 2009. — Т. 11.
  • R. Frucht, J. E. Graver, M. E. Watkins. The groups of the generalized Petersen graphs // Proceedings of the Cambridge Philosophical Society. — 1971. — Т. 70. — doi:10.1017/S0305004100049811.
  • Peter McMullen. The regular polyhedra of type {p, 3} with 2p vertices // Geometriae Dedicata. — 1992. — Т. 43, вып. 3. — doi:10.1007/BF00151518.
  • Arjana Žitnik, Boris Horvat, Tomaž Pisanski. All generalized Petersen graphs are unit-distance graphs. — 2010. — Т. 1109. — (IMFM preprints).
  • R. M. Foster. Geometrical circuits of electrical networks // Transactions of the American Institute of Electrical Engineers. — 1932. — Т. 51. — doi:10.1109/T-AIEE.1932.5056068.
  • I. Z. Bouwer, W. W. Chernoff, B. Monson, Z. Star. The Foster Census. — Charles Babbage Research Centre, 1988.
  • H. S. M. Coxeter. Self-dual configurations and regular graphs // Bulletin of the American Mathematical Society. — 1950. — Т. 56. — doi:10.1090/S0002-9904-1950-09407-5.
  • M. Zacharias. Untersuchungen über ebene Konfigurationen (124, 163) // Deutsche Mathematik. — 1941. — Т. 6.
  • Ed Pegg Jr. Cubic Symmetric Graphs. — Mathematical Association of America, 2003.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.