Mineurs interdits pour les graphiques de genre délimités

Il est bien connu que $K_5$ et $K_{3,3}$ sont des mineurs interdits pour les graphes planaires. Il existe des centaines de mineurs interdits pour les graphiques intégrables sur un tore. Le nombre de mineurs interdits pour les graphes intégrables à la surface du genre g est une fonction exponentielle de g . Ma question est la suivante:

Existe-t-il un graphe explicite $G_t$ sur t sommets (qui n'est pas un graphe complet) tel que $G_t$ est un mineur interdit pour les graphes noyables à la surface du genre g , où t est fonction de g ?

EDIT: J'ai réalisé que le théorème suivant est connu:

Pour chaque surface Σ il existe un entier r tel que ne s'incruste pas dans Σ. $K_{3,r}$

Donc, je cherche qui n'est pas un graphe complet, pas un graphe bipartite complet. $G_t$

graph-theory co.combinatorics graph-minor algebraic-topology Shiva Kintali
la source

Donc, vous voulez une famille infinie de graphes paramétrés, joliment construits (autres que des graphiques complets) qui sont des mineurs interdits pour les surfaces de tous les genres?

Derrick Stolee

@Derrick. Oui. Précisément.

Shiva Kintali

Ensuite, je reformulerais la question en utilisant ces termes: "Existe-t-il une famille (simple à construire) de graphes

{H_{g} : g \geq 1}

$\{ H_g : g \geq 1\}$ sorte que

soit un mineur minimal interdit pour les graphiques intégrables sur une surface du genre

? "

H_{g} ≇ K_{n}

$H_g \not\cong K_n$

g

$g$

Derrick Stolee

La contrainte "

ne sont pas des mineurs de

" ne peut pas être ce que vous voulez. S'ils ne sont pas mineurs de

, alors

est planaire et ne peut être un mineur interdit pour aucun genre supérieur.

K_{5}

$K_5$

K_{3, 3}

$K_{3,3}$

G

$G$

G

$G$

G

$G$

David Eppstein

@DavidEppstein J'ai supprimé mes modifications. Essentiellement, je recherche des obstructions "différentes" de

K_{5}

$K_5$

K_{33}

$K_{33}$

Shiva Kintali

Réponses:

L'union disjointe de exemplaires de (ou $n$ $K_5$ $K_{3,3}$ ) est un mineur minimal interdit pour les graphes du genre ; il en va de même pour un graphe dans lequel certaines de ces copies partagent un seul sommet, de sorte que les blocs du graphe sont ou . Cela découle des résultats de J. Battle, F. Harary, Y. Kodama et JWT Youngs, "Additivité du genre d'un graphique", Bull. Amer. Math. Soc. 68 (1962) 565-568, et est déjà suffisant pour montrer qu'il y a au moins exponentiellement beaucoup de mineurs interdits. $n-1$ $K_5$ $K_{3,3}$

Bojan Mohar, "Une obstruction à l'intégration de graphiques dans des surfaces", Discrete Math. 78 (1989) 135–142, énumère le graphique formé à partir de en supprimant un cycle à 4 comme ayant le genre 2. Puisque est toroïdal, cela signifie que ou l'un de ses sous-graphiques couvrant est une obstruction à l'intégration de tore, et que les graphiques qui ont copies de ce graphique comme leurs blocs ont le genre . $K_8$ $K_7$ $K_8\setminus C_4$ $n$ $2n$

Mohar montre également que le graphique formé à partir d'un cycle en connectant le sommet 0 à tous les sommets pairs et le sommet 1 à tous les sommets impairs a un "genre relatif" d'au moins . Le graphique est plan, mais je pense que le genre relatif signifie que le cycle doit être un visage; ou vous pouvez ajouter un autre sommet au graphique, connecté à tous les sommets du cycle, pour le forcer efficacement à être une face. C'est peut-être plus proche du genre de chose que vous voulez. Mais je ne pense pas qu'il montre que ces graphiques sont des mineurs minimes interdits. $(2k+2)$ $\lceil k/2\rceil$

David Eppstein
la source

Votre dernier paragraphe sur

cycle

est ce que je recherche. Merci. J'accepte votre réponse.

(2 k + 2)

$(2k+2)$

Shiva Kintali