Decomposição de gráficos conectados em k em componentes conectados (k + 1)

15

Um gráfico conectado pode ser decomposto em seus componentes biconetados. Essa árvore do ponto de corte do bloco é única. Da mesma forma, os gráficos biconetados podem ser decompostos em componentes triconetados. A árvore SPQR correspondente descreve todos os cortes de 2 vértices no gráfico e é determinada exclusivamente a partir dele.

Esse processo não generaliza para maior conectividade. Por exemplo, dado um gráfico triconetadoG, pode haver várias "árvores" descrevendo todos os cortes de três vértices de G.

Existem classes especiais de gráficos tais que kgráficos interligados (nessas classes) podem ser decompostos exclusivamente emk+1componentes conectados.

Observe que minha pergunta é um pouco diferente dessa pergunta .

Shiva Kintali
fonte

Respostas:

8

O artigo recente a seguir parece estar relacionado à sua pergunta:

Conectividade e estrutura de árvores em gráficos finitos
Johannes Carmesin, Reinhard Diestel, Fabian Hundertmark, Maya Stein

http://arxiv.org/abs/1105.1611

Daniel Marx
fonte