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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории графов под конференсным графом понимается сильно регулярный граф с параметрами 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 и два других,

каждое из которых повторяется (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.