График Брауэра – Хемерса - Brouwer–Haemers graph - Wikipedia

График Брауэра – Хемерса
Вершины	81
Края	810
Радиус	2
Диаметр	2
Обхват	3
Автоморфизмы	233,280
Хроматическое число	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]

Связанные графики

Граф Брауэра – Хемерса - первый в бесконечном семействе графов Графики Рамануджана определяется как обобщенный Графики Пэли над полями характеристики три.^[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. Брауэр, Андрис, «График Брауэра – Хемерса», Описание различных графиков, получено 2019-02-11
2. Подеста, Рикардо А .; Видела, Денис Э. (2018), Спектры обобщенных графов Пэли и приложения, arXiv:1812.03332
3. Брауэр, А.Э.; Хемерс, В. Х. (1992), "Структура и единственность (81,20,1,6) сильно регулярного графа", Сборник статей в честь Джека ван Линта, Дискретная математика, 106/107: 77–82, Дои:10.1016 / 0012-365X (92) 90532-К, МИСТЕР  1181899
4. Clark, L.H .; Entringer, R.C .; McCanna, J. E .; Секели, Л. А. (1991), «Экстремальные задачи для локальных свойств графов» (PDF), Австралазийский журнал комбинаторики, 4: 25–31, МИСТЕР  1129266
5. Вайсштейн, Эрик В. «График Брауэра – Хемерса». MathWorld.
6. Бондаренко, Андрей В .; Радченко, Данило В. (2013), "О семействе сильно регулярных графов с ${\displaystyle \lambda =1}$", Журнал комбинаторной теории, Серия B, 103 (4): 521–531, arXiv:1201.0383, Дои:10.1016 / j.jctb.2013.05.005, МИСТЕР  3071380
7. Гаго-Варгас, Хесус; Хартильо-Эрмосо, Мария Изабель; Мартин-Моралес, Хорхе; Уча-Энрикес, Хосе Мария (2006), «Судоку и основы Грёбнера: не только divertimento", в Ганже, Виктор Г .; Майр, Эрнст У .; Ворожцов, Евгений В. (ред.), Компьютерная алгебра в научных вычислениях, 9-й международный семинар, CASC 2006, Кишинев, Молдова, 11-15 сентября 2006 г., Труды, Конспект лекций по информатике, 4194, Springer, стр. 155–165, Дои:10.1007/11870814_13
8. Герцберг, Агнес М.; Мурти, М. Рам (2007), «Квадраты судоку и хроматические многочлены» (PDF), Уведомления Американского математического общества, 54 (6): 708–717, МИСТЕР  2327972