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

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

Граф Брауэра — Хемерса
Вершин 81
Рёбер 810
Диаметр 2
Обхват 3
Автоморфизмы 233280
Хроматическое число 7
Свойства

Построение

Граф Брауэра — Хемерса имеет несколько связанных алгебраических построений. Одно из самых простых построений — как обобщённый граф Пэли порядка 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].

References

  1. Andries Brouwer. Brouwer–Haemers graph.
  2. Ricardo A. Podestá. The spectra of generalized Paley graphs and applications. — 2018. arXiv:1812.03332.
  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.
  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.
  5. Weisstein, Eric W. Brouwer–Haemers Graph (англ.) на сайте Wolfram MathWorld.
  6. 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.
  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.
  8. Agnes M. Herzberg, M. Ram Murty. Sudoku squares and chromatic polynomials // Notices of the American Mathematical Society. — 2007. Т. 54, вып. 6. С. 708–717.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.