Граф Науру

Шаблон:Граф У теорії графів, граф Науру — симетричний двочастковий кубічний граф з 24 вершинами і 36 ребрами. Він був названий Девідом Епштейном на честь двадцятизіркового прапору Науру.

Його хроматичне число — 2, хроматичний індекс — 3, діаметр — 4, радіус — 4 та обхват — 6. Він так само містить 3-вершинно-зв'язний та 3-реберно-зв'язний графи.

Найменші кубічні графи з числами схрещень 1-8 відомі (Шаблон:OEIS). Найменший граф з числом схрещень 8 — граф Науру. Існує 5 неізоморфних кубічних графів 24-го порядку з числом перетину 8. Один з них являє собою граф Маꥳ, також відомий як (3-7)-клітина.

Конструкція

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

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

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

Алгебраїчні властивості

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

Узагальнений граф Петерсена 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). Таким чином, граф Науру є одним з семи симетричних узагальнених графів Петерсена. Серед цих семи графів кубічний граф $G(4,1)$, граф Петерсена $G(5,2)$, граф Мебіуса — Кантора $G(8,3)$, додекаедрічний граф $G(10,2)$ і граф Дезарга $G(10,3)$.

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

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

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

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

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

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

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

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

Топологічні властивості

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

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

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

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

Геометричні властивості

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

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

Історія

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

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