Граф Клебша

Материал из WikiGrapp
Перейти к:навигация, поиск

Граф Клебша (Clebsch graph) — 10-регулярный граф на 16 вершинах. Вершинам ставятся в соответствие подмножества A \subset \{1,2,3,4,5\} такие, что |A| \leq 2. Две вершины A и A' будут смежными тогда и только тогда, когда для их симметрической разности справедливы неравенства

2 \leq |A \triangle A'| \leq 3.

Этот граф является дистанционно-транзитивным, а также для любой вершины u ее окрестность N(u) в графе Клебша изоморфна дополнению графа Петерсена. Дополнение графа Клебша изоморфно графу Гринвуда-Глисона E_{3}.

Литература

  • Mulder H.M. The interval function of a graph, Mathematical Centre Tracts 132. — Amsterdam, 1980.