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

Граф Петерсена (J.Petersen, 1891) — граф $P_{10}(=P)$, допускающий следующее представление:

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

Гиперсетью Петерсена называется граф $H{P}_n=Q_{n-3}\times P$, где $Q_{n-3}$ — $(n-3)$-мерный гиперкуб.

$n$-складной граф Петерсена ($n$-folded Petersen graph) есть граф $F{P}_n=\underset{n}{\underbrace{P\times \cdots \times P}}$. Здесь $\times$ обозначает декартово произведение.

Литература

• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

• Харари Ф. Теория графов. — М.: Мир, 1973.

• Workshop. Utrecht, 1993 // Lect. Notes Comp. Sci., 1994, vol. 790.