Сімейство Петерсена

Петерсонове сімейство в теорії графів є множиною з семи графів без орієнтації, яка включає в себе граф Петерсена та повний граф K₆. Петерсонове сімейство названо на честь датского математика Юліуса Петерсена.

Петерсонове сімейство. Повний граф K₆ вгорі, граф Петерсена внизу. Блакитні риски відповідають Δ-Y або Y-Δ перетворенням між графами сімейства.

Будь-який граф сімейства може бути перетворений на будь-який інший граф у сімействі Y-Δ перетворенням, яке замінює трикутник на вершину степіня три або навпаки (див. рисунок). Ці сім графів утворюють заборонені підграфи для незачепленого вкладення графів, тобто такі графи, які можуть бути вбудовані в тривимірний простір так, щоб не було двох зчеплених циклів у графі. Робертсон та ін. вирішили питання Сакса, показавши, що графи, вкладені без зачеплень — це в точності ті графи, які не мають членів петерсенова сімейства як міноров. Вони також є одними з заборонених підграфів для YΔY-редукованих графів.

Примітки

1. ; ; (1993), Linkless embeddings of graphs in 3-space, Bulletin of the American Mathematical Society, 28 (1): 84—89, arXiv:math/9301216, doi:10.1090/S0273-0979-1993-00335-5, MR 1164063.
2. (1983), On a spatial analogue of Kuratowski's Theorem on planar graphs – an open problem, у Horowiecki, M.; Kennedy, J. W.; Sysło, M. M. (ред.), Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, т. 1018, Springer-Verlag, с. 230—241, doi:10.1007/BFb0071633.
3. Truemper, Klaus (1992), Matroid Decomposition (PDF), Academic Press, с. 100—101, архів оригіналу (PDF) за 29 серпня 2017, процитовано 20 грудня 2017.
4. Yu, Yaming (2006), More forbidden minors for wye-delta-wye reducibility (PDF), Electronic Journal of Combinatorics, 13 (1): #R7, архів оригіналу (PDF) за 28 червня 2011, процитовано 20 грудня 2017.