Граф Петерсена

Граф Петерсена (J.Petersen, 1891) - граф [math]\displaystyle{ P_{10}( = P) }[/math], допускающий следующее представление:

Пусть [math]\displaystyle{ \Omega = \{1,2,3,4,5\} }[/math] --- 5-элементное множество. Вершины графа [math]\displaystyle{ P_{10} }[/math] --- это двухэлементные подмножества из [math]\displaystyle{ \Omega }[/math]. Две вершины в [math]\displaystyle{ P_{10} }[/math] смежны тогда и только тогда, когда соответствующие им подмножества не пересекаются. Г.П. представляет собой сумму 1-фактора и 2-фактора, состоящего из двух 5-циклов. Г.П. есть наименьший 3-регулярный граф с обхватом 5, без гамильтонова цикла, с повышенным хроматическим числом.

Гиперсетью Петерсена называется граф [math]\displaystyle{ HP_{n} = Q_{n-3} \times P }[/math], где [math]\displaystyle{ Q_{n-3} }[/math] --- [math]\displaystyle{ (n-3) }[/math]-мерный гиперкуб.

[math]\displaystyle{ n }[/math]-складной граф Петерсена ([math]\displaystyle{ n }[/math]-folded Petersen graph) есть граф [math]\displaystyle{ FP_{n} = \underbrace{P \times \cdots \times P}_{n} }[/math]. Здесь [math]\displaystyle{ \times }[/math] обозначает декартово произведение.

Литература

[Харари],

[Лекции],

[WG'93]