Граф Науру

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

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

Така можлива комбінаторна побудова графу Науру. Візьміть три неоднакові об'єкти і розмістіть їх у чотири неоднакові коробки, не більше одного об'єкта в коробці. Є 24 способи, щоб розподілити об'єкти, відповідно 24 вершинам графу. Якщо можливо перейти з одного положення в інше, переміщуючи рівно один об'єкт із його поточного місця розташування у порожнє місце, то вершини, що відповідають двом положенням, поєднуються ребром. Як результат, графом переходу станів є граф Науру.

Група автоморфізмів графу Науру — група порядку 144.[5] Вона ізоморфна прямому добутку симетричних груп S₄ і S₃ і діє транзитивно на вершинах по краях і на дугах графу. Тому графік Науру — симетричний граф. Він має автоморфізми, які переміщують будь-яку вершину до будь-якої іншої вершини і будь-яке ребро до будь-якого іншого ребра. За даними перепису Фостера, граф Науру є єдиним кубічно-симетричним графом на 24 вершинах.[2]

Узагальнений граф Петерсена G(n, k) є вершинно-транзитивним тоді, і тільки тоді, коли n = 10 і k = 2 або якщо k² ≡ ± 1 (mod n) і є реберно-транзитивним тільки в наступних випадках: (n, k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5).[6] Таким чином, граф Науру є одним з семи симетричних узагальнених графів Петерсена. Серед цих семи графів кубічний граф ${\displaystyle G(4,1)}$, граф Петерсена ${\displaystyle G(5,2)}$, граф Мебіуса — Кантора ${\displaystyle G(8,3)}$, додекаедрічний граф ${\displaystyle G(10,2)}$ і граф Дезарга ${\displaystyle G(10,3)}$.

Граф Науру — це граф Келі групи S₄, симетричної групи перестановок чотирьох елементів, що породжується трьома різними способами перестановки першого елементу з трьома іншими: (1 2), (1 3) і (1 4).

Характеристичний поліном графу Науру дорівнює

${\displaystyle (x-3)(x-2)^{6}(x-1)^{3}x^{4}(x+1)^{3}(x+2)^{6}(x+3),\ }$

що робить його цілим графом, тобто графом спектр якого складається повністю з цілих чисел.

1-планарний граф, що має 8 перетинів.

Симетричний тор . Тор формується, топологічно, склеюванням протилежних країв правильного шестикутника один до одного.

Узагальнений граф Петерсена. Розфарбовування і перестановки показують, що це граф Келі S4.

Матриця суміжності. Кожне ребро представляє два записи однакового кольору, що є симетричними до головної діагоналі.

Симетричне вкладення графу Науру родової 4 поверхні, з шістьма двенадцатикутними об'єктами.

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

Одне з цих двох вкладень утворює тор, тому граф Науру — це тороїдальний граф: він складається з 12 шестикутних граней разом з 24 вершинами і 36 ребрами графу Науру. Двоїстий граф — це вкладення симетричного 6-регулярного графу з 12 вершинами і 36 ребрами.

Інші симетричні вкладення графу Науру мають шість дванадцятикутних граней, які утворюють поверхню 4 роду . Двоїстий граф може бути сформований з простого графу.

Як і у всіх узагальнених графах Петерсена, граф Науру можна представити точками на площині таким чином, що сусідні вершини знаходяться на одиниці відстані один від одного. Це граф одиничної відстані.[8] Такими є тільки узагальнені графи Петерсена G (n, р), вони не можуть бути представлені таким чином, що симетрії малюнка утворюють циклічну групу порядку n. Замість цього, одинична відстань графу має діедральну групу Dih₆ як групу її симетрії.

Граф Науру є графом одиничних відстаней.

Першою людиною, що написала про граф Науру був Рональд Фостер, він зробив це у спробі зібрати усі кубічні симетричні графи.[9] Список кубічних симетричних графів зараз носить ім'я Перепис Фостера і всередині цього списку граф Науру має номер F24A, але не має конкретного імені.[10] У 1950 р. Гарольд Коксетер описав граф у другий раз, даючи ствердження Гамільтона для ілюстрації цієї статті, та описуючи його як граф Леві проєктивної конфігурації, описаного Захарієм.[11][12]

У 2003, Ед Пегг написав у своєму онлайн-МАА рубрику про те, що F24A заслуговує на назву, але не запропонував її.[13] Нарешті, у 2007 році, Девід Епштейн використав ім'я Граф Науру, тому що прапор Республіки Науру має 12-кінцеву зірку, аналогічну до тієї, що з'являється в конструкції графу як узагальнений граф Петерсена.[1]