P4-Связный граф

Материал из WikiGrapp
Перейти к:навигация, поиск

P_{4}-Связный граф (P_{4}-Connected graph) — граф G = (V,E), у которого для каждого разбиения множества V на непересекающиеся подмножества V_{1} и V_{2} найдется некоторая цепь без хорд с четырьмя вершинами и тремя ребрами (т.е. P_{4}), которая содержит вершины как из V_{1}, так и из V_{2}.

Различают следующие классы графов с простыми P_{4}-структурами: P_{4}-сводимые (reducible), P_{4}-растяжимые (extendible), P_{4}-разреженные (sparse).

Литература

  • Workshop. Cadenabbia, 1996 // Lect. Notes Comp. Sci., 1997, vol. 1197.