График Брауэра – Хемерса - Википедия - Brouwer–Haemers graph

График Брауэра – Хемерса
Брауэр Хемерс graph.svg
Вершины81
Края810
Радиус2
Диаметр2
Обхват3
Автоморфизмы233,280
Хроматическое число7
Характеристики
Таблица графиков и параметров

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

Строительство

Граф Брауэра – Хемерса имеет несколько связанных алгебраических конструкций. Один из самых простых - это обобщенная степень 4. Граф Пэли: его можно определить, создав вершину для каждого элемента в конечное поле и ребро для каждых двух элементов, которые отличаются на четвертая степень.[1][2]

Характеристики

Граф Брауэра – Хемерса является единственным сильно регулярный граф с параметрами (81, 20, 1, 6). Это означает, что он имеет 81 вершину, 20 ребер на вершину, 1 треугольник на ребро и 6 путей длиной два, соединяющих каждую несмежную пару вершин.[3] Как сильно регулярный граф с третьим параметром, равным 1, граф Брауэра – Хемерса обладает тем свойством, что каждое ребро принадлежит единственному треугольнику; то есть это локально линейный. Нахождение больших плотных графов с этим свойством - одна из формулировок Проблема Ружи – Семереди.[4]

Помимо того, что он очень регулярный, это дистанционно-транзитивный граф.[5]

История

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

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

Граф Брауэра – Хемерса - первый в бесконечном семействе графов Графики Рамануджана определяется как обобщенный Графики Пэли над полями характеристики три.[2] С График ладьи и График игр, это один из трех возможных сильно регулярных графов, параметры которых имеют вид .[6]

Его следует отличать от Судоку граф, другой 20-регулярный граф с 81 вершиной. График судоку получен из Судоку головоломки, создавая вершину для каждого квадрата головоломки и соединив два квадрата ребром, когда они принадлежат одной строке, столбцу или блок головоломки. У него много 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), "О семействе сильно регулярных графов с ", Журнал комбинаторной теории, Серия 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