Конференсный граф

Конференсный граф — сильно регулярный граф с параметрами v, k = (v − 1)/2, λ = (v − 5)/4, и μ = (v − 1)/4. Этот граф соответствует симметричной конференсной матрице, и, следовательно, его порядок v должен быть сравним с 1 по модулю 4 и быть суммой двух квадратов.

Известно, что конференсные графы существуют для всех малых значений v, удовлетворяющих ограничениям, например, v = 5, 9, 13, 17, 25, 29, и (графы Пэли) для всех степеней простых чисел, сравнимых с 1 по модулю 4. Однако существует много значений v, для которых ограничения выполняются, но существуют ли конференсные графы, неизвестно.

Собственные значения конференсных графов не обязательно целые числа, что необычно для сильно регулярных графов. Если граф связан, одно собственное значение равно k и два других,

${\frac {-1\pm {\sqrt {v}}}{2}},$

каждое из которых повторяется (v − 1)/2 раз.

Литература

• Brouwer, A. E., Cohen, A. M., Neumaier, A. Distance Regular Graphs. — Berlin, New York: Springer-Verlag, 1989. — ISBN 3-540-50619-5, 0-387-50619-5.