Петерсонове сімейство
Петерсонове сімейство в теорії графів є множиною з семи графів без орієнтації, яка включає в себе граф Петерсена та повний граф K6. Петерсонове сімейство названо на честь датского математика Юліуса Петерсена.
Будь-який граф сімейства може бути перетворений на будь-який інший граф у сімействі Y-Δ перетворенням, яке замінює трикутник на вершину степіня три або навпаки (див. рисунок). Ці сім графів утворюють заборонені підграфи для незачепленого вкладення графів, тобто такі графи, які можуть бути вбудовані в тривимірний простір так, щоб не було двох зчеплених циклів у графі.[1] Робертсон та ін. вирішили питання Сакса, показавши, що графи, вкладені без зачеплень — це в точності ті графи, які не мають членів петерсенова сімейства як міноров.[2] Вони також є одними з заборонених підграфів для YΔY-редукованих графів.[3][4]
Примітки ред.
- ↑ Robertson, Neil; Seymour, P. D.; Thomas, Robin (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.
- ↑ Sachs, Horst (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.
- ↑ Truemper, Klaus (1992), Matroid Decomposition (PDF), Academic Press, с. 100—101, архів оригіналу (PDF) за 29 серпня 2017, процитовано 20 грудня 2017.
- ↑ Yu, Yaming (2006), More forbidden minors for wye-delta-wye reducibility (PDF), Electronic Journal of Combinatorics, 13 (1): #R7, архів оригіналу (PDF) за 28 червня 2011, процитовано 20 грудня 2017.