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

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

Построение

Граф Брауэра — Хемерса имеет несколько связанных алгебраических построений. Одно из самых простых построений — как обобщённый граф Пэли порядка 4. Его можно определить путём выбора каждой вершины из конечного поля $GF(81)$, а в качества рёбер берутся каждые два элемента, отличающиеся на четвёртую степеньШаблон:R.

Свойства

Граф Брауэра — Хемерса является единственным сильно регулярным графом с параметрами (81, 20, 1, 6). Это означает, что он имеет 81 вершину, 20 рёбер на вершину, 1 треугольник на ребро и путь, соединяющий каждые две несмежные вершины имеет длину 6Шаблон:R. Как сильно регулярный граф с третьим параметром 1, граф Брауэра — Хемерса обладает свойством, что любое ребро принадлежит единственному треугольнику. То есть он локально линеен. Поиск больших плотных графов с этим свойством является одной из формулировок проблемы Ружи — СемередиШаблон:R.

Будучи строго регулярным, граф дистанционно-транзитивенШаблон:R.

История

Хотя Брауэр писал, что построения этого графа является «фольклорным» и цитировал раннюю статью 1964 года по латинским квадратам Дейла М. МеснераШаблон:R, граф назван именами Андреаса Брауэра и Уиллема Х. Хемерса, которые в 1992 году опубликовали доказательство, что он единственный строго регулярный граф с такими параметрамиШаблон:R.

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

Граф Брауэра — Хемерса является первым в бесконечном семействе графов Рамануджана, определённых как обобщение графов Пэли над полем характеристики триШаблон:R. Вместе с $3\times 3$ ладейным графом и графом Геймса он является одним из трёх возможных сильно регулярных графов, параметры которых имеют вид $((n^2+3n-1{)}^2,n^2(n+3),1,n(n+1))$Шаблон:R.

Граф следует отличать от графа судоку, другого 20-регулярного графа с 81 вершиной. Граф судоку получается из головоломки Судоку, если разместить вершину в каждой ячейке судоку и соединить рёбрами вершины, которые находятся в той же строке, в том же столбце или $3\times 3$ блоке головоломки. Граф имеет много клик с 9 вершинами и требует 9 цветов для любой раскраски. Раскраска в 9 цветов этого графа описывает решение головоломки судокуШаблон:R. В качестве контраста, в графе Брауэра — Хемерса наибольшими кликами являются треугольники и для раскраски нужно лишь 7 цветовШаблон:R.