Разложение k-связных графов на (k + 1) -связные компоненты

15

Связный граф можно разложить на его двусвязные компоненты. Это дерево сечений блоков является уникальным. Аналогично, двусвязные графы можно разложить на трехсвязные компоненты. Соответствующее дерево SPQR описывает все 2-вершинные срезы графа и однозначно определяется из его графа.

Этот процесс не распространяется на более высокую связность. Например, учитывая трехсвязным графа , может быть несколько «деревья» , описывающие все разрезы 3- х вершин из .граммграмм

Существуют ли специальные классы графов, такие, что связные графы (в этих классах) можно однозначно разложить на их -связные компоненты.КК+1

Обратите внимание, что мой вопрос немного отличается от этого вопроса .

Шива Кинтали
источник

Ответы:

8

Следующая недавняя статья, кажется, связана с вашим вопросом:

Связность и древовидная структура в конечных графах
Йоханнес Кармезин, Рейнхард Дистел, Фабиан Хундертмарк, Майя Стейн

http://arxiv.org/abs/1105.1611

Даниэль Маркс
источник