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

Граф Брауера — Хемерса
Вершин	81
Ребер	810
Радіус	2
Діаметр	2
Обхват	3
Автоморфізм	233280
Хроматичне число	7
Властивості	сильно регулярний дистанційно-транзитивний граф Рамануджана локально лінійний

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

Побудова

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

Властивості

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

Як строго регулярний, граф є дистанційно-транзитивним[5].

Історія

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

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

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

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

Примітки

1. Andries Brouwer. Brouwer–Haemers graph.
2. Ricardo A. Podestá. The spectra of generalized Paley graphs and applications. — 2018. — arXiv:1812.03332.
3. Brouwer A. E., Haemers W. H. Structure and uniqueness of the (81,20,1,6) strongly regular graph // Discrete Mathematics. — 1992. — Т. 106/107. — С. 77–82. — DOI:10.1016/0012-365X(92)90532-K.
4. Clark L. H., Entringer R. C., McCanna J. E., Székely L. A. Extremal problems for local properties of graphs // The Australasian Journal of Combinatorics. — 1991. — Т. 4. — С. 25–31.
5. Weisstein, Eric W. Brouwer–Haemers Graph(англ.) на сайті Wolfram MathWorld.
6. Andriy V. Bondarenko, Danylo V. Radchenko. On a family of strongly regular graphs with ${\displaystyle \lambda =1}$ // Journal of Combinatorial Theory. — 2013. — Т. 103, вип. 4. — С. 521–531. — DOI:10.1016/j.jctb.2013.05.005.
7. Jesús Gago-Vargas, Maria Isabel Hartillo-Hermoso, Jorge Martín-Morales, Jose Maria Ucha-Enríquez. Sudokus and Gröbner bases: Not only a divertimento // Computer Algebra in Scientific Computing, 9th International Workshop, CASC 2006, Chisinau, Moldova, September 11-15, 2006, Proceedings / Victor G. Ganzha, Ernst W. Mayr, Evgenii V. Vorozhtsov. — Springer, 2006. — Т. 4194. — С. 155–165. — (Lecture Notes in Computer Science). — DOI:10.1007/11870814_13.
8. Agnes M. Herzberg, M. Ram Murty. Sudoku squares and chromatic polynomials // Notices of the American Mathematical Society. — 2007. — Т. 54, вип. 6. — С. 708–717.