Mineurs interdits pour les graphiques à largeur d'arbre limitée

17

Cette question est similaire à l' une de mes précédentes. Il est connu que est un mineur interdit pour les graphiques de largeur d'arbre au plus .Kt+2t

Existe-t-il une famille infinie de graphiques bien paramétrés et bien construits (autres que les graphiques complets et les graphiques en grille) qui sont des mineurs minimes interdits pour les graphiques de chaque largeur d'arbre. Autrement dit, existe-t-il un graphe explicite sur sommets (qui n'est pas un graphe complet) tel que est un mineur interdit pour les graphes de largeur d'arbre au plus , où est fonction de ?GrrGrrrt

Les ensembles complets de mineurs interdits sont connus pour les graphiques de la largeur d'arbre au maximum trois. Voir cet article Wikipedia pour plus de détails.

Est-ce que l'ensemble complet des mineurs interdits de graphiques de largeur d'arbre au plus quatre est connu?

Shiva Kintali
la source
Dans la première question, avec «mineur interdit», vous voulez dire «mineur interdit minimal», n'est-ce pas? sinon les grilles sont un exemple.
Diego de Estrada
1
Oui. Je voulais dire mineure mineure interdite.
Shiva Kintali
2
Vous avez fait deux commentaires augmentant votre question, un ici et un sous une réponse; il serait préférable d'inclure les changements dans la question elle-même afin que les gens n'aient pas à lire les différents fils de commentaires pour comprendre la question.
joriki
@joriki J'ai mis à jour la question.
Shiva Kintali

Réponses:

9

Si G est formé à partir d'un plus petit graphique H qui n'est pas une clique en ajoutant deux sommets x et y, de telle sorte que x et y ne soient pas adjacents mais adjacents à tous les autres sommets de G, alors . Car, dans toute décomposition arborescente de G , x et y ont des sous-arbres disjoints ou ils ont des sous-arbres qui se chevauchent. S'ils ont des sous-arbres disjoints, tous les autres sous-arbres doivent inclure le chemin le plus court entre les arbres pour x et y , d'où il résulte que la largeur de l'arbre est n - 2tw(g)=tw(H)+2gXyXyn-2; l'hypothèse que n'est pas une clique peut alors être utilisée pour montrer que n - 2 t w ( H ) + 2 . Alternativement, si x et y ont des sous-arbres qui se chevauchent, chaque autre sommet doit avoir un sous-arbre qui touche l'intersection des deux sous-arbres de x et y , et nous pouvons limiter la décomposition de l'arbre à cette intersection, donnant une décomposition d'arbre dans laquelle x et y participer à chaque nœud d'arbre.Hn-2tw(H)+2XyXyXy

Cela implique que le graphe hyperoctaédrique avec 2 k nœuds est un mineur minimal interdit pour la largeur 2 k - 3 . Car, le graphe octaédrique K 2 , 2 , 2 est un mineur minimal interdit pour la largeur trois, à partir duquel l'argument ci-dessus montre que le graphe hyperoctaédrique a une largeur 2 k - 2K2,2,2,2k2k-3K2,2,22k-2. Et si une contraction ou une suppression de bord est effectuée dans le graphique hyperoctaédrique, les symétries du graphique nous permettent de supposer que l'opération se produit sur l'un des douze bords de l'octaèdre de base, provoquant sa largeur et la largeur de tous les hyperoctaèdres construit à partir de lui pour diminuer.

(L'autre classe de graphiques que vous devriez inclure dans votre question avec les graphiques complets sont les graphiques de grille. Une grille a une largeur d'arbre r . Elle est distincte des mineurs de graphique complets car elle est plane et n'a donc pas de mineur complet avec plus de quatre sommets. Ce n'est pas un mineur minimal interdit, car certains petits changements (comme la contraction des sommets des coins) ne modifient pas la largeur de son arborescence.)r×rr

David Eppstein
la source
Oui. Permet d'exclure les graphiques en grille.
Shiva Kintali
13

4

Aaron Sterling
la source