Граф Брауера — Хемерса
| Граф Брауера — Хемерса | |
|---|---|
 | |
| Вершин | 81 |
| Ребер | 810 |
| Радіус | 2 |
| Діаметр | 2 |
| Обхват | 3 |
| Автоморфізм | 233280 |
| Хроматичне число | 7 |
| Властивості | |
Граф Брауера — Хемерса — 20-регулярний неорієнтований граф з 81 вершиною та 810 ребрами. Це сильно регулярний, дистанційно-транзитивний граф та граф Рамануджана. Хоча його побудова є математичним фольклором, граф названо іменами Андреаса Брауера та Вілема Х. Хемерса, які довели його єдиність як строго регулярного графа.
Граф Брауера — Хемерса має кілька пов'язаних алгебричних побудов. Одна з найпростіших побудов — як узагальненого графа Пелі порядку 4. Його можна визначити вибором кожної вершини зі скінченного поля , а як ребра беруться кожні два елементи, що відрізняються на четвертий степінь[1][2].
Граф Брауера — Хемерса є єдиним регулярним графом з параметрами (81, 20, 1, 6). Це означає, що він має 81 вершину, 20 ребер на вершину, 1 трикутник на ребро і шлях, що з'єднує кожні дві несуміжні вершини, має довжину 6[3]. Як регулярний граф із третім параметром 1, граф Брауера — Хемерса має властивість, що будь-яке ребро належить єдиному трикутнику. Тобто він локально лінійний. Пошук великих щільних графів із цією властивістю є одним із формулювань проблеми Ружі — Семереді[4].
Як строго регулярний, граф є дистанційно-транзитивним[5].
Хоча Брауер писав, що побудова цього графа є «фольклором» і цитував ранню статтю 1964 року про латинські квадрати Дейла М. Меснера[1], граф названо іменами Андреаса Брауера та Вілема Х. Хемерса, які 1992 року опублікували доведення, того, що це єдиний строго регулярний граф із такими параметрами[3].
Граф Брауера — Хемерса є першим у нескінченному сімействі графів Рамануджана, визначених як узагальнення графів Пелі над полем характеристики 3[2]. Разом із туровим графом і графом Геймса він є одним із трьох можливих сильно регулярних графів, параметри яких мають вигляд [6].
Граф слід відрізняти від графа судоку, іншого 20-регулярного графа з 81 вершиною. Граф судоку виходить із головоломки судоку, якщо розмістити вершину в кожній комірці судоку і з'єднати ребрами вершини, розташовані в тому ж рядку, в тому ж стовпці або блоці головоломки. Граф має багато клік із 9 вершинами і вимагає 9 кольорів для будь-якого розфарбування. Розфарбування в 9 кольорів цього графа визначає розв'язок головоломки судоку[7][8]. Як контраст, у графі Брауера — Хемерса найбільшими кліками є трикутники і для розфарбування потрібно лише 7 кольорів[5].
- ↑ а б Andries Brouwer. Brouwer–Haemers graph.
- ↑ а б Ricardo A. Podestá. The spectra of generalized Paley graphs and applications. — 2018. — arXiv:1812.03332.
- ↑ а б 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.
- ↑ 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.
- ↑ а б Weisstein, Eric W. Brouwer–Haemers Graph(англ.) на сайті Wolfram MathWorld.
- ↑ Andriy V. Bondarenko, Danylo V. Radchenko. On a family of strongly regular graphs with // Journal of Combinatorial Theory. — 2013. — Т. 103, вип. 4. — С. 521–531. — DOI:10.1016/j.jctb.2013.05.005.
- ↑ 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.
- ↑ Agnes M. Herzberg, M. Ram Murty. Sudoku squares and chromatic polynomials // Notices of the American Mathematical Society. — 2007. — Т. 54, вип. 6. — С. 708–717.
