Граф Клебша

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

[math]\displaystyle{ 2 \leq |A \triangle A'| \leq 3. }[/math]

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

Литература

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