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 .
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 ?
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?
fonte
Respostas:
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)+2 G x y x y n−2 ; 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.H n−2≥tw(H)+2 x y x y x y
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,… 2k 2k−3 K2 , 2 , 2 2 k - 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 × r r
fonte
Nas obstruções esparsas e na determinação exata da largura da árvore , Lucena afirma que, na tese de doutorado de Sanders , "75 ou menos menores proibidos para a largura da árvore são dados, e acredita-se, embora não esteja provado, que isso possa constituir todo o conjunto de obstruções".≤ 4
fonte