Граф призмы

---

Хотя геометрически звёздчатые многоугольники также служат гранями другой последовательности (самопересекающихся и невыпуклых) призматических многогранников, графы этих звёздчатых призм изоморфны графам призм и не образуют отдельной последовательности графов.

Графы призм являются примерами обобщённых графов Петерсена с параметрами GP(n,1). Графы также можно образовать как прямое произведение цикла и единичного ребра^[1].

Как и многие вершинно-транзитивные графы, призматические графы можно построить как графы Кэли. Диэдральная группа порядка n является группой симметрий правильного n-угольника на плоскости. Она действует на n-угольник вращениями и отражениями. Группа может быть сгенерирована двумя элементами, вращением на угол ${\displaystyle 2\pi /n}$ и одним отражением, и граф Кэли этой группы с этим генерирующим множеством является графом призмы. Абстрактно группа имеет задание ${\displaystyle \langle r,f\mid r^{n},f^{2},(rf)^{2}\rangle }$ (где r — это вращение, а f — отражение) и граф Кэли имеет r и f (или r, r⁻¹ и f) в качестве генераторов ^[1]

Граф n-угольной призмы с нечётным n можно построить как циркулянтный граф ${\displaystyle C_{2n}^{2,n}}$, однако это построение не работает для чётных значений n ^[1].

Граф n-угольной призмы имеет 2n вершин и 3n рёбер. Графы являются регулярными кубическими графами. Поскольку призма имеет симметрии, переводящие любую вершину в любую другую, графы призм являются вершинно-транзитивными графами. Являясь полиэдральными графами, эти графы также являются вершинно 3-связными планарными графами. Любой граф призмы имеет гамильтонов цикл^[2].

Среди всех двусвязных кубических графов графы призм имеют с точностью до постоянного множителя наибольшее возможное число 1-разложений графа. 1-разложение — это разбиение множества рёбер графа на три совершенных паросочетания, или, эквивалентно, рёберная раскраска графа тремя цветами. Любой двусвязный кубический граф с n вершинами имеет O(2^n/2) 1-разложений, а граф призмы имеет Ω(2^n/2) 1-разложений ^[3].

---