Граф Брауера — Хемерса

Граф Брауера — Хемерса — 20-регулярний неорієнтований граф з 81 вершиною та 810 ребрами. Це сильно регулярний, дистанційно-транзитивний граф та граф Рамануджана. Хоча його побудова є математичним фольклором, граф названо іменами Андреаса Брауера та Вілема Х. Хемерса, які довели його єдиність як строго регулярного графа.

Побудова

Граф Брауера — Хемерса має кілька пов'язаних алгебричних побудов. Одна з найпростіших побудов — як узагальненого графа Пелі порядку 4. Його можна визначити вибором кожної вершини зі скінченного поля $GF(81)$, а як ребра беруться кожні два елементи, що відрізняються на четвертий степіньШаблон:R.

Властивості

Граф Брауера — Хемерса є єдиним регулярним графом з параметрами (81, 20, 1, 6). Це означає, що він має 81 вершину, 20 ребер на вершину, 1 трикутник на ребро і шлях, що з'єднує кожні дві несуміжні вершини, має довжину 6Шаблон:R. Як регулярний граф із третім параметром 1, граф Брауера — Хемерса має властивість, що будь-яке ребро належить єдиному трикутнику. Тобто він локально лінійний. Пошук великих щільних графів із цією властивістю є одним із формулювань проблеми Ружі — СемередіШаблон:R.

Як строго регулярний, граф є дистанційно-транзитивнимШаблон:R.

Історія

Хоча Брауер писав, що побудова цього графа є «фольклором» і цитував ранню статтю 1964 року про латинські квадрати Дейла М. МеснераШаблон:R, граф названо іменами Андреаса Брауера та Вілема Х. Хемерса, які 1992 року опублікували доведення, того, що це єдиний строго регулярний граф із такими параметрамиШаблон:R.

Пов'язані графи

Граф Брауера — Хемерса є першим у нескінченному сімействі графів Рамануджана, визначених як узагальнення графів Пелі над полем характеристики 3Шаблон:R. Разом із $3\times 3$ туровим графом і графом Геймса він є одним із трьох можливих сильно регулярних графів, параметри яких мають вигляд $((n^2+3n-1{)}^2,n^2(n+3),1,n(n+1))$ Шаблон:R.

Граф слід відрізняти від графа судоку, іншого 20-регулярного графа з 81 вершиною. Граф судоку виходить із головоломки судоку, якщо розмістити вершину в кожній комірці судоку і з'єднати ребрами вершини, розташовані в тому ж рядку, в тому ж стовпці або блоці $3\times 3$ головоломки. Граф має багато клік із 9 вершинами і вимагає 9 кольорів для будь-якого розфарбування. Розфарбування в 9 кольорів цього графа визначає розв'язок головоломки судокуШаблон:R. Як контраст, у графі Брауера — Хемерса найбільшими кліками є трикутники і для розфарбування потрібно лише 7 кольорівШаблон:R.