Verbotene Minderjährige für beschränkte Gattungsgraphen

Es ist bekannt, dass und für ebene Graphen verbotene Minderjährige sind. Es gibt Hunderte verbotener Minderjähriger für Grafiken, die auf einem Torus eingebettet werden können . Die Anzahl verbotener Minderjähriger für Graphen, die auf der Oberfläche der Gattung g eingebettet werden können, ist eine Exponentialfunktion von g . Meine Frage lautet wie folgt: $K_5$ $K_{3,3}$

Gibt es einen expliziten Graphen auf t Eckpunkten (der kein vollständiger Graph ist), so dass ein verbotener Nebeneffekt für Graphen ist, die auf der Oberfläche der Gattung g eingebettet werden können , wobei t eine Funktion von g ist ? $G_t$ $G_t$

EDIT: Ich erkannte, dass der folgende Satz bekannt ist:

Für jede Fläche Σ existiert eine ganze Zahl r, so dass nicht in Σ eingebettet ist. $K_{3,r}$

Also suche ich nach , das kein vollständiger Graph ist, kein vollständiger zweigeteilter Graph. $G_t$

graph-theory co.combinatorics graph-minor algebraic-topology Shiva Kintali
quelle

Sie möchten also eine schön aufgebaute, parametrisierte, unendliche Familie von Diagrammen (außer vollständigen Diagrammen), die für Oberflächen aller Gattungen verboten sind?

Derrick Stolee

@Bohrturm. Ja. Genau.

Shiva Kintali

{H_{g} : g \geq 1}

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

H_{g} ≇ K_{n}

$H_g \not\cong K_n$

g

$g$

Die Bedingung " und sind keine Minderjährigen von " kann nicht das sein, was Sie möchten. Wenn sie keine Minderjährigen von , ist planar und kann für keine höhere Gattung ein verbotener Minderjähriger sein.

K_{5}

$K_5$

K_{3, 3}

$K_{3,3}$

G

$G$

G

$G$

G

$G$

David Eppstein

@DavidEppstein Ich habe meine Änderungen entfernt. Im Wesentlichen suche ich nach Hindernissen, die sich von und "unterscheiden" .

K_{5}

$K_5$

K_{33}

$K_{33}$

Shiva Kintali

Antworten:

Die disjunkte Vereinigung von Kopien von (oder ) ist ein minimal verbotener Nebeneffekt für die Graphen der Gattung ; Das gleiche gilt für ein Diagramm, in dem einige dieser Kopien einen einzelnen Scheitelpunkt gemeinsam haben, sodass die Blöcke des Diagramms oder . Dies ergibt sich aus den Ergebnissen von J. Battle, F. Harary, Y. Kodama und JWT Youngs, "Additivity of the Genus of a Graph", Bull. Amer. Mathematik. Soc. 68 (1962) 565–568 und reicht bereits aus, um zu zeigen, dass es zumindest exponentiell viele verbotene Minderjährige gibt. $n$ $K_5$ $K_{3,3}$ $n-1$ $K_5$ $K_{3,3}$

Bojan Mohar, "Ein Hindernis für das Einbetten von Graphen in Oberflächen", Discrete Math. 78 (1989) 135–142, listet den aus gebildeten auf, indem ein 4-Zyklus mit der Gattung 2 entfernt wird. Da toroidal ist, bedeutet dies, dass entweder oder einer seiner übergreifenden Untergraphen eine Behinderung der Torus-Einbettung darstellt , und die Graphen, deren Blöcke Kopien dieses Graphen enthalten, haben die Gattung . $K_8$ $K_7$ $K_8\setminus C_4$ $n$ $2n$

Mohar zeigt auch, dass der Graph, der aus einem -Zyklus durch Verbinden des Scheitelpunkts 0 mit allen geraden Scheitelpunkten und des Scheitelpunkts 1 mit allen ungeraden Scheitelpunkten gebildet wird, eine "relative Gattung" von mindestens . Die Grafik ist planar, aber ich denke, relative Gattung bedeutet, dass der Zyklus ein Gesicht sein muss; Oder Sie können dem Diagramm einen weiteren Scheitelpunkt hinzufügen, der mit allen Scheitelpunkten des Zyklus verbunden ist, um ihn effektiv zu einer Fläche zu machen. Vielleicht ist das näher an der Art von Dingen, die Sie wollen. Aber ich glaube nicht, dass er zeigt, dass diese Grafiken minimal verbotene Minderjährige sind. $(2k+2)$ $\lceil k/2\rceil$

David Eppstein
quelle

Ihr letzter Absatz über Zyklus ist das, wonach ich suche. Vielen Dank. Ich akzeptiere deine Antwort.

(2 k + 2)

$(2k+2)$

Shiva Kintali