Граф Брауера Хемерса 20 регулярний неорієнтований граф з 81 вершиною та 810 ребрами Це сильно регулярний дистанційно тра

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

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

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

Побудова

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

Властивості

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

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

Історія

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

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

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

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

Примітки

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 $\lambda =1$ // . — 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.

[b-1] Andries Brouwer. Brouwer–Haemers graph.

[pv-2] Ricardo A. Podestá. The spectra of generalized Paley graphs and applications. — 2018. — arXiv:1812.03332.

[bh-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.

[cems-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.

[mw-5] Weisstein, Eric W. Brouwer–Haemers Graph(англ.) на сайті Wolfram MathWorld.

[br-6] Andriy V. Bondarenko, Danylo V. Radchenko. On a family of strongly regular graphs with $\lambda =1$ // . — 2013. — Т. 103, вип. 4. — С. 521–531. — DOI:10.1016/j.jctb.2013.05.005.

[ghmu-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.

[hm-8] Agnes M. Herzberg, M. Ram Murty. Sudoku squares and chromatic polynomials // Notices of the American Mathematical Society. — 2007. — Т. 54, вип. 6. — С. 708–717.