Menores proibidos para gráficos de gênero limitados

É bem conhecido que $K_5$ e $K_{3,3}$ são proibidos menores para grafos planares. Existem centenas de menores proibidos para gráficos incorporados em um toro. O número de menores proibidos para gráficos incorporáveis na superfície do gênero g é uma função exponencial de g . Minha pergunta é a seguinte:

Existe um gráfico explícito nos t vértices (que não é um gráfico completo) tal que é um menor proibido para gráficos incorporáveis na superfície do gênero g , onde t é uma função de g ? $G_t$ $G_t$

EDIT: Eu percebi que o seguinte teorema é conhecido:

Para toda superfície exists existe um número inteiro r tal que não incorpora Σ. $K_{3,r}$

Então, eu estou procurando por que não é um gráfico completo, não um gráfico bipartido completo. $G_t$

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

Então, você quer uma família infinita de gráficos, bem estruturada e parametrizada (exceto gráficos completos) que são proibidos menores para superfícies de todos os gêneros?

Derrick Stolee

@Derrick. Sim. Precisamente.

Shiva Kintali

Em seguida, reformularia a pergunta usando os seguintes termos: "Existe uma família de gráficos (simples de construir)

para que

seja um menor mínimo proibido para gráficos incorporados em uma superfície de gênero

? "

{H_{g} : g \geq 1}

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

H_{g} ≇ K_{n}

$H_g \not\cong K_n$

g

$g$

Derrick Stolee

A restrição "

não são menores de

" não pode ser o que você deseja. Se eles não são menores de

, então

é plano e não pode ser um menor proibido para nenhum gênero superior.

K_{5}

$K_5$

K_{3, 3}

$K_{3,3}$

G

$G$

G

$G$

G

$G$

9788 David Eppstein #

@DavidEppstein removi minhas modificações. Basicamente, estou procurando obstruções "diferentes" de

K_{5}

$K_5$

K_{33}

$K_{33}$

Shiva Kintali

Respostas:

A união disjunta de cópias de (ou ) é uma menor mínima proibida para os gráficos do gênero ; o mesmo se aplica a um gráfico no qual algumas dessas cópias compartilham um único vértice, de modo que os blocos do gráfico são ou . Isto resulta dos resultados em J. Battle, F. Harary, Y. Kodama e JWT Youngs, "Aditividade do gênero de um gráfico", Bull. Amer. Matemática. Soc. 68 (1962) 565-568, e já é suficiente para mostrar que há pelo menos exponencialmente muitos menores proibidos. $n$ $K_5$ $K_{3,3}$ $n-1$ $K_5$ $K_{3,3}$

Bojan Mohar, "Uma obstrução à incorporação de gráficos em superfícies", Discrete Math. 78 (1989) 135-142, lista o gráfico formado a partir de removendo um ciclo 4 como tendo o gênero 2. Como é toroidal, isso significa que ou um de seus subgrafos de extensão é uma obstrução para incorporação de toro, e que os gráficos que possuem cópias deste gráfico como seus blocos têm o gênero . $K_8$ $K_7$ $K_8\setminus C_4$ $n$ $2n$

Mohar também mostra que o gráfico formado a partir de um ciclo conectando o vértice 0 a todos os vértices pares e o vértice 1 a todos os vértices ímpares tem "gênero relativo" pelo menos . O gráfico é plano, mas acho que o gênero relativo significa que o ciclo deve ser um rosto; ou você pode adicionar outro vértice ao gráfico, conectado a todos os vértices do ciclo, para efetivamente forçá-lo a ser uma face. Talvez isso seja mais próximo do tipo de coisa que você deseja. Mas não acho que ele mostre que esses gráficos são menores proibidos. $(2k+2)$ $\lceil k/2\rceil$

David Eppstein
fonte

Seu último parágrafo sobre o ciclo

é o que estou procurando. Obrigado. Estou aceitando sua resposta.

(2 k + 2)

$(2k+2)$

Shiva Kintali 9/11/11