Введение

Концепция в теории графов

В теории графов сильно регулярный граф (SRG) – это регулярный граф G = (V, E) с v вершинами и степенью k, такой что для некоторых заданных целых чисел:
каждые две смежные вершины имеют λ общих соседей, и
каждые две несмежные вершины имеют μ общих соседей.
Такой сильно регулярный граф обозначается srg(v, k, λ, μ); его "параметры" – это числа (v, k, λ, μ). Его дополнение также является сильно регулярным: это srg(v, v − k − 1, v − 2 − 2k + μ, v − 2k + λ). Сильно регулярный граф является дистанционно-регулярным графом с диаметром 2, когда μ не равно нулю. Он является локально линейным графом, когда λ = 1.

Этимология

Сильно регулярный граф обозначается как srg(v, k, λ, μ) в литературе. По общепринятому соглашению, графики, удовлетворяющие определению тривиально, исключаются из детальных исследований и списков сильно регулярных графов. К ним относятся непересекающееся объединение одного или нескольких полных графов одинакового размера и их дополнения, а также полные многодольные графы с независимыми множествами одинакового размера. Андрис Брауэр и Хендрик ван Малдегем (см. #References) используют альтернативное, но полностью эквивалентное определение сильно регулярного графа, основанное на спектральной теории графов: сильно регулярный граф – это конечный регулярный граф, имеющий ровно три собственных значения, только одно из которых равно степени k и имеет кратность 1. Это автоматически исключает полные графы (которые имеют только два различных собственных значения, а не три) и несвязные графы (для которых кратность степени k равна числу различных связных компонент, что, следовательно, превышает единицу). В большей части литературы, включая работы Брауэра, большее собственное значение обозначается как r (с кратностью f), а меньшее – как s (с кратностью g).

История

Сильно регулярные графы были введены Р. К. Бозе в 1963 году. Они опирались на более ранние работы 1950-х годов в тогда только зарождающейся области спектральной теории графов.

Примеры

Цикл длины 5 является srg(5, 2, 0, 1). Граф Петерсена является srg(10, 3, 0, 1). Граф Клебша является srg(16, 5, 0, 2). Граф Шриханде является srg(16, 6, 2, 2), который не является дистанционно-транзитивным графом. Квадратный граф ладей n × n, то есть линейный граф сбалансированного полного двудольного графа Kn,n, является srg(n², 2n − 2, n − 2, 2). Параметры для совпадают с параметрами графа Шриханде, но эти два графа не изоморфны. Линейный граф полного графа Kn является . Графы Чанга являются srg(28, 12, 6, 4), что то же самое, что и линейный граф K8, но эти четыре графа не изоморфны. Каждый обобщенный квадрангл порядка (s, t) дает srg((s + 1)(st + 1), s(t + 1), s − 1, t + 1) в качестве своего линейного графа. Например, GQ(2, 4) дает srg(27, 10, 1, 5) в качестве своего линейного графа. Граф Шлефли является srg(27, 16, 10, 8). Граф Хоффмана — Синглтона является srg(50, 7, 0, 1). Граф Симса — Гевиртца является srg(56, 10, 0, 2). Граф M22, также известный как граф Меснера, является srg(77, 16, 0, 4). Граф Брауэра — Хаемерса является srg(81, 20, 1, 6). Граф Хигмана — Симса является srg(100, 22, 0, 6). Локальный граф Маклафлина является srg(162, 56, 10, 24). Граф Кэмерона является srg(231, 30, 9, 3). Граф Берлекампа — ван Линта — Сейделя является srg(243, 22, 1, 2). Граф Маклафлина является srg(275, 112, 30, 56). Граф Пейли порядка q является srg(q, (q − 1)/2, (q − 5)/4, (q − 1)/4). Наименьший граф Пейли с q = 5 является циклом 5 (выше). Самодополнительные дуготранзитивные графы сильно регулярны. Сильно регулярный граф называется примитивным, если и сам граф, и его дополнение связны. Все вышеперечисленные графы примитивны, иначе или . Задача Конвея о 99 графах состоит в построении srg(99, 14, 1, 2). Неизвестно, существует ли граф с этими параметрами, и Джон Хортон Конвей предложил приз в 1000 долларов за решение этой задачи.

Графики без треугольников

Сильно регулярные графы с λ = 0 не содержат треугольников. Помимо полных графов на менее чем 3 вершинах и всех полных двудольных графов, только семь, перечисленных ранее (пентагон, граф Петерсена, граф Клебша, граф Хоффмана-Синглтона, граф Гвиртца, граф Меснера M22 и граф Хигмана-Симса), являются известными на данный момент.

Геодезические графики

Каждый сильно регулярный граф с λ = μ является геодезическим графом, то есть графом, в котором для любых двух вершин существует единственный невзвешенный кратчайший путь. Единственные известные сильно регулярные графы с λ = μ – это графы, где μ = 0, а значит, и треугольников нет. Они называются графами Мура и рассматриваются ниже более подробно. Другие комбинации параметров, такие как (400, 21, 2, 1), пока не были исключены. Несмотря на продолжающиеся исследования свойств, которыми обладал бы сильно регулярный граф с λ = μ, неизвестно, существуют ли еще какие-либо такие графы, и даже конечно ли их количество.