Запрещенные миноры для графов с ограниченным родом

Хорошо известно, что $K_5$ и $K_{3,3}$ являются запрещенными минорами для плоских графов. Существуют сотни запрещенных миноров для графов, встраиваемых в тор. Количество запрещенных миноров для графов, встраиваемых на поверхность рода g, является экспоненциальной функцией от g . Мой вопрос заключается в следующем:

Существует ли явный граф $G_t$ на t вершинах (который не является полным графом), такой, что $G_t$ является запрещенным минором для графов, вложимых в поверхность рода g , где t является функцией от g ?

РЕДАКТИРОВАТЬ: я понял, что следующая теорема известна:

Для любой поверхности Σ существует такое целое число r , что $K_{3,r}$ не вкладывается в Σ.

Итак, я ищу $G_t$ который не является полным графом, а не полным двудольным графом.

graph-theory co.combinatorics graph-minor algebraic-topology Шива Кинтали
источник

Итак, вы хотите красиво сконструированное, параметризованное, бесконечное семейство графов (кроме полных графов), которые являются запрещенными минорами для поверхностей любого рода?

Деррик Столи

@Derrick. Да. Точно.

Шива Кинтали

Тогда я бы перефразировал вопрос, используя такие термины: «Существует ли (простое в построении) семейство графов

так что

является минимальным запрещенным минором для графов, вложимых в поверхность рода

?»

{H_{g} : g \geq 1}

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

H_{g} ≇ K_{n}

$H_g \not\cong K_n$

g

$g$

Деррик Столи

Ограничение «

не являются минорами

» не может быть тем, что вы хотите. Если они не миноры группы

, то группа

планарна и не может быть запрещенной группой для более высокого рода.

K_{5}

$K_5$

K_{3, 3}

$K_{3,3}$

G

$G$

G

$G$

G

$G$

Дэвид Эппштейн

@DavidEppstein Я удалил свои модификации. По сути, я ищу препятствия, которые «отличаются» от

K_{5}

$K_5$

K_{33}

$K_{33}$

Шива Кинтали

Ответы:

Несвязное объединение копий (или ) является минимальным запрещенным минором для графов рода ; то же самое верно для графа, в котором некоторые из этих копий имеют общую вершину, так что блоками графа являются или . Это следует из результатов J. Battle, F. Harary, Y. Kodama и JWT Youngs, «Аддитивность рода графа», Bull. Amer. Математика Soc. $n$ $K_5$ $K_{3,3}$ $n-1$ $K_5$ $K_{3,3}$ 68 (1962) 565–568, и этого уже достаточно, чтобы показать, что по крайней мере экспоненциально много запрещенных несовершеннолетних.

Боян Мохар, "Препятствие для вложения графов в поверхности", Дискрет. 78 (1989) 135–142, перечисляет график, образованный из путем удаления 4-цикла как имеющего род 2. Поскольку является тороидальным, это означает, что либо либо один из его охватывающих подграфов является препятствием вложение торов, и графы, которые имеют копий этого графа в качестве своих блоков, имеют род . $K_8$ $K_7$ $K_8\setminus C_4$ $n$ $2n$

Мохар также показывает, что граф, образованный из -цикла путем соединения вершины 0 со всеми четными вершинами и вершины 1 со всеми нечетными вершинами, имеет «относительный род», по крайней мере, . График плоский, но я думаю, что относительный род означает, что цикл должен быть лицом; или вы можете добавить в граф другую вершину, связанную со всеми вершинами цикла, чтобы эффективно заставить ее быть гранью. Может быть, это ближе к тому, что вы хотите. Но я не думаю, что он показывает, что эти графики являются минимально запрещенными несовершеннолетними. $(2k+2)$ $\lceil k/2\rceil$

Дэвид Эппштейн
источник

Ваш последний абзац о цикле

- это то, что я ищу. Благодарю. Я принимаю ваш ответ.

(2 k + 2)

$(2k+2)$

Шива Кинтали