Menores proibidos para gráficos com largura de árvore limitada

17

Esta pergunta é semelhante a uma das minhas perguntas anteriores. Sabe-se que é um menor proibido para gráficos de largura de árvore no máximo t .Kt+2t

Existe uma família infinita de gráficos, bem parametrizada e bem construída (que não sejam gráficos completos e gráficos de grade) que são menores mínimos proibidos para gráficos de todas as larguras de árvores. Em outras palavras, há um gráfico explícito em r vértices (que não é um gráfico completo) de tal modo que L R é um menor proibido por gráficos de treewidth no máximo r , onde r é uma função de t ?GrrGrrrt

Os conjuntos completos de menores proibidos são conhecidos por gráficos de largura de árvore no máximo três. Veja este artigo da Wikipedia para mais detalhes.

É conhecido o conjunto completo de menores proibidos de gráficos de largura de árvore no máximo quatro?

Shiva Kintali
fonte
Na primeira pergunta, com "menor proibido" você quer dizer "menor proibido mínimo", não é? caso contrário, os gráficos de grade são um exemplo.
Diego de Estrada
11
Sim. Eu quis dizer menor proibido mínimo.
Shiva Kintali 17/11/11
2
Você fez dois comentários aumentando a sua pergunta, um aqui e outro com uma resposta; seria preferível incluir as alterações na própria pergunta para que as pessoas não precisem ler vários tópicos de comentários para entender a pergunta.
joriki
@joriki Atualizei a pergunta.
Shiva Kintali

Respostas:

9

Se G é formado a partir de um gráfico menor H que não é um clique adicionando dois vértices x e y, de modo que x e y não são adjacentes um ao outro, mas adjacentes a todos os outros vértices de G, então . Pois, em qualquer decomposição em árvore de G , x e y têm subárvores disjuntas ou subárvulas sobrepostas. Se eles têm sub-árvores de disjunção, todas as outras sub-árvores tem que incluir o caminho mais curto entre as árvores para x e y , a partir do qual se segue que a treewidth é n - 2tw(G)=tw(H)+2Gxyxyn2; a suposição de que não é um clique pode então ser usada para mostrar que n - 2 t w ( H ) + 2 . Como alternativa, se x e y têm subárvores sobrepostas, todos os outros vértices precisam ter uma subárvore que toque a interseção das duas subárvores de x e y , e podemos restringir a decomposição da árvore a essa interseção, fornecendo uma decomposição na qual x e y participe de todos os nós da árvore.Hn2tw(H)+2xyxyxy

Isso implica que o gráfico hiperoctaédrico com 2 k nós é um mínimo proibido mínimo para a largura 2 k - 3 . Pois, o gráfico octaédrico K 2 , 2 , 2 é um menor mínimo proibido para a largura três, a partir do qual o argumento acima mostra que o gráfico hiperoctaédrico tem largura 2 k - 2K2,2,2,2k2k3K2,2,22k-2. E se qualquer contração ou exclusão de aresta for realizada no gráfico hiperoctaédrico, as simetrias do gráfico permitem assumir que a operação está acontecendo com uma das doze arestas no octaedro base, causando sua largura e a largura de todas as hiperoctaedras. construído a partir dele para diminuir.

(A outra classe de gráficos você deve ser incluindo na sua pergunta juntamente com os gráficos completos são os gráficos de grade. Uma grade tem treewidth r . É separado dos menores grafo completo porque o seu plano e, portanto, não tem menor completo com mais no entanto, não é um menor mínimo proibido, porque algumas pequenas alterações (como a contratação dos vértices de canto) não alteram sua largura de árvore.)r×rr

David Eppstein
fonte
Sim. Permite excluir gráficos de grade.
Shiva Kintali